Fast and Slow Pointers (Cycle Detection)

Two pointers on one list: slow moves 1 node per step, fast moves 2. The speed difference exposes structure (middle, cycles) in O(n) time and O(1) space. Node has .value and .next, last .next is None.

Find the middle (one pass)

• Start both at head; loop while fast and fast.next; slow = slow.next, fast = fast.next.next.
• When fast runs off the end, slow sits at the middle (it walked half as far).
• Even length: this stops on the second middle; stop one step earlier for the first.
• O(n) time, O(1) space, reads the list once instead of one-and-a-half times.

Cycle detection (Floyd’s)

• Same 1-and-2 movement. If fast hits None, no cycle. If slow is fast, cycle found.
• Compare with is (same node object), never == (equal values gives false positives).
• Why they meet: once both are in the loop, fast gains exactly 1 step on slow each round, so the gap shrinks by 1 and must hit 0 within one lap. A 3-step fast could jump over 0, so keep it 1-and-2.
• A seen-set also detects cycles but costs O(n) memory; two pointers stay O(1).

flowchart LR
    A["1"] --> B["2"]
    B --> C["3"]
    C --> D["4"]
    D --> E["5"]
    E --> C

Find the cycle’s start

• Phase 1: run Floyd’s to a meeting point inside the loop.
• Phase 2: reset one pointer to head, keep the other at the meeting point, advance both by 1; they meet at the entrance.
• Intuition: with tail length a and meeting point b into the loop, fast = 2·slow forces the distance from the meeting point back to the start to equal a — so both walkers cover a and arrive together.
• Reset the head pointer, not the meeting pointer.

Numbers, not just lists

• Any “next value from current value” rule is an invisible linked list; a repeat is a cycle.
• Happy number: replace n with the sum of squares of its digits; reaches 1 (happy) or loops. 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 loops; 19 -> 82 -> 68 -> 100 -> 1 is happy.
• slow = rule(slow), fast = rule(rule(fast)); stop when fast == 1 (happy) or slow == fast (loop). Use == here — plain integers, not node objects.

Pitfalls

• Null checks: guard fast and fast.next before fast.next.next, or crash on None. and short-circuits, so order matters.
• is for nodes, == for numbers.
• Speed ratio must be 1-and-2; other ratios can skip the meeting.
• Empty / single-node lists: loop body never runs, returns correctly — check the condition before moving.

Summary table