CONCEPT · 60 minutes
Fast and slow pointers, in-place reversal, and the cycle-detection trick that reveals how well you reason about pointer manipulation.
Early in the Python orchestration framework, I added a "retry chain" feature. When a task failed, the worker would walk a linked sequence of fallback strategies — retry with backoff, retry with reduced payload, escalate to a dead-letter queue. The feature worked in testing. In production, one worker hung at 100% CPU. No log messages, no exceptions. Just a spinning process.
I attached a debugger. The worker was stuck in an infinite while node: loop walking the retry
chain. A bug in the chain-builder had accidentally pointed the last fallback node back at the
first one. The list had a cycle, and my naive traversal had no way to detect it.
I knew Floyd's cycle-detection algorithm in the abstract — tortoise and hare, fast pointer and slow pointer — but I had never needed it under pressure until that moment. I implemented it in ten lines of Python and the bug was gone in twenty minutes. The real lesson was not "know Floyd's algorithm." It was: when you understand pointer manipulation at the right depth, bugs that look like magic become mechanical to diagnose.
That depth is what this module teaches. Linked lists are the simplest data structure where pointer reasoning is inescapable. If you can reverse a list in-place and detect a cycle without scratching your head, you understand mutation and state well enough to reason about much harder systems — dependency graphs, task chains, streaming pipelines.
A linked list is a chain of nodes. Each node holds a value and a pointer to the next node:
In Python that is a single class with two fields:
No library. No import. Three lines to build a test list.
Think of a linked list as a chain of wagons, not an array. You cannot jump to wagon 42 by index — you walk from the engine, one coupling at a time. That single constraint is why every linked-list technique reduces to: what do I need to track as I walk? The answer is almost always one, two, or three pointers walking at different speeds or offsets. The rest of this module is those three patterns.
The tortoise-and-hare trick: run two pointers through the list simultaneously, one moving one node at a time (slow), one moving two nodes at a time (fast). Because they advance at different rates, they end up at different positions after the same number of steps.
Finding the middle node in one pass is the simplest use. When fast reaches the end, slow is at the middle — it has traveled half as far.
graph LR
subgraph "After 2 steps"
A["[1]"] --> B["[2]"] --> C["[3]"] --> D["[4]"] --> E["[5]"]
slow["slow → [3]"]
fast["fast → [5]"]
endCycle detection uses the same structure, but the exit condition changes. If the list has no cycle, fast falls off the end. If it does have a cycle, fast will eventually lap slow and catch up — they will point to the same node inside the cycle.
When this bites: it is tempting to write while fast.next and fast.next.next instead of while fast and fast.next. That fails when fast itself is None — you get AttributeError: 'NoneType' object has no attribute 'next'. Check fast first, then fast.next. This ordering matters every time you advance two nodes.
Nth node from the end uses fixed lag instead of different speeds. Advance fast by n
steps first, then advance both together. When fast falls off, slow is exactly n from the end.
I used a dummy node there. That is the third pattern — hold it for a moment.
Reversal is the canonical test of pointer-mutation reasoning. The idea: walk the list once, and
on each step, flip the arrow that points forward so it points backward. You need three pointers:
the node before the one you are flipping (prev), the node you are flipping (curr), and the
node after it (next_node) — saved before you destroy the forward reference.
Think of it as a three-step shuffle at each position: save, flip, advance.
graph TD
A["Before: 1 → 2 → 3 → None\nprev=None, curr=1"]
B["Step 1: save next=2, flip 1→None\nadvance: prev=1, curr=2"]
C["Step 2: save next=3, flip 2→1\nadvance: prev=2, curr=3"]
D["Step 3: save next=None, flip 3→2\nadvance: prev=3, curr=None"]
E["After: None ← 1 ← 2 ← 3\nreturn prev (new head = 3)"]
A --> B --> C --> D --> EAfter the loop, curr is None (we walked off the end) and prev is the last node visited —
the new head. The recursive form is more compact but uses the call stack to hold prev implicitly:
When this bites: the recursive form uses O(n) stack space — one frame per node. For a list of 100,000 nodes, Python's default recursion limit (1000) overflows. The iterative form uses O(1) space. Reach for iterative unless the list is provably small.
Some list operations are awkward when the answer might require modifying the head node itself.
The dummy head is a sentinel node you prepend before the real list. You operate on the chain
starting from dummy.next, and at the end you return dummy.next as the new head. The dummy
absorbs the edge case.
Imagine building a paper chain. The dummy is the first link you hold in your hand — it never
ends up in the finished chain, but it gives you something to attach to while you build. When
you are done, you hand back dummy.next and discard the starting link.
Merging two sorted lists is the textbook use. Pick the smaller head from each list, attach it to the chain, advance that pointer. Repeat until one list is empty, then append the rest.
The line current.next = l1 or l2 is a Python shorthand: whichever of the two is not None
gets appended. Because both input lists are sorted, everything remaining is already in order.
The pattern that works: whenever a problem says the answer might start at a different node than the input, reach for a dummy head. The dummy makes the "output is empty" and "output starts at a new node" cases identical — there is no special branch.
Close the examples and answer these from memory before moving on.
n + 1 rather than n when advancing fast?Reflective prompt: The dummy head pattern appears in merge, remove-nth, and several other list problems. What is the underlying property that makes a sentinel node useful here — what changes if the answer requires a new head vs. the same head? Think about what edge case disappears when you add the dummy.
Application-level questions on linked list pointer patterns
1. The `while fast and fast.next` guard in Floyd's cycle detection checks `fast` before `fast.next`. Why does the order matter?
Correct Answer: B
Python's `and` short-circuits left-to-right. If `fast` is None, Python stops before evaluating `fast.next` — preventing the AttributeError. Writing `while fast.next and fast.next.next` would crash the moment `fast` becomes None on the penultimate step.
2. After one iteration of the iterative reversal loop on `1 -> 2 -> 3 -> None` (starting with prev=None, curr=node(1)), what values do `prev` and `curr` hold at the end of that iteration?
Correct Answer: B
One iteration: save next_node=node(2), flip node(1).next to None, advance prev=node(1), advance curr=node(2). After one full iteration, prev points to the just-flipped node and curr has advanced to the next unprocessed node.
3. In `merge_two_lists`, what problem does the dummy head solve?
Correct Answer: B
Without a dummy, you need to special-case the first node attachment (there is nothing to attach to yet). The dummy node acts as a guaranteed existing node; `current.next = ...` always works, and `dummy.next` at the end always points to the real head, whether or not any nodes were attached.
4. For a list of 7 nodes, on which node (1-indexed) does `slow` land after `find_middle` completes?
Correct Answer: B
With 7 nodes: step 1 — slow=2, fast=3; step 2 — slow=3, fast=5; step 3 — slow=4, fast=7; step 4 — fast.next is None so the while condition fails. Slow lands on node 4, the true middle of a 7-node list.
5. In Linked List Cycle II, after the fast/slow meeting point is found, why does resetting one pointer to `head` and advancing both one step at a time find the cycle entry?
Correct Answer: B
This is the mathematical core of Floyd's algorithm. Let F = distance from head to cycle entry. Floyd's meeting condition proves that a pointer from head and a pointer from the meeting node will both reach the cycle entry in exactly F more steps — they converge there.
6. You reverse a linked list of 10,000 nodes using the recursive implementation. What happens?
Correct Answer: C
Python's default recursion limit is 1000 frames. A 10,000-node list requires 10,000 recursive calls and raises RecursionError. The iterative version uses O(1) space and handles any list length.
7. In `remove_nth_from_end`, why does the code advance `fast` by `n + 1` steps rather than `n` steps before the main loop?
Correct Answer: B
To delete a node in a singly linked list you need a pointer to its predecessor, so you can do `slow.next = slow.next.next`. Advancing fast by n+1 instead of n positions slow exactly one node before the target when fast reaches the end.
The task: implement a function that detects not just whether a linked list has a cycle, but where the cycle begins — the entry node. This is the classic "Linked List Cycle II" problem.
Background: Floyd's algorithm guarantees that when slow and fast meet inside the cycle, the distance from the meeting point to the cycle entry equals the distance from the list head to the cycle entry. Use that fact to find the entry in a second pass.
Work through both phases before revealing a hint.
Hint 1 (nudge): Phase 1 is exactly has_cycle from earlier — run slow and fast until they meet or fast falls off. Save the meeting node when they collide, because you need its position in phase 2.
Hint 2 (the insight): After phase 1, reset one pointer to head and leave the other at the meeting node. Advance both one step at a time. The mathematical proof (not required to memorize) guarantees they converge at the cycle entry. Implement the second loop and trust the invariant.
Worked solution: study it only after your own attempt runs.
Extend it: once detect_cycle works, write a helper that breaks the cycle — walk to the
node just before the entry and set its next to None. That is exactly the fix the
orchestration retry chain needed: detect the rogue back-pointer and sever it.