Sweaty Imposter

Fast & Slow Pointers (Floyd's) Pattern

CodingMid2 min read · 4 problemsUpdated

Two pointers move at different speeds through a linked structure to detect cycles or find midpoints.

When to Use It

Cycle detection in linked lists, finding cycle start, middle of linked list, happy number.

Classic example: Linked list cycle detection.

How It Works

Floyd's tortoise and hare exploits the fact that in a cyclic structure, a pointer moving at speed 2 will eventually lap a pointer moving at speed 1, and they must meet inside the cycle. The math: once both pointers are in the cycle of length C, the fast pointer closes the gap by 1 per step, so meeting happens within C steps after both enter.

Finding the cycle's start uses a second phase, after detection, reset one pointer to the head and move both at speed 1; they meet at the cycle entrance. This works because the distance from head to entrance equals the distance from the meeting point to entrance (mod cycle length), a consequence of the speed-2 vs speed-1 relationship.

Beyond linked lists, the pattern applies anywhere you have a functional graph (each node has exactly one outgoing edge): happy number iteration, finding the duplicate in an array where indices and values form a chain, or any sequence x_{n+1} = f(x_n) that may cycle.

Key Insight

In any cycle, a 2x-speed pointer closes the gap by 1 per step, guaranteeing a meeting in O(cycle length): and the head-to-cycle-start distance equals the meet-to-cycle-start distance, which falls out of the speed ratio.

1234567slowfast
Slow moves 1 step, fast moves 2; they meet inside any cycle.

Templates

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
        // cycle detected
        break;
    }
}

Common Pitfalls

  • Checking fast and fast.next for null in the wrong order, NPE'ing when fast is already null.
  • Advancing slow before checking equality, which can miss the meeting on the first iteration of cycle detection.
  • For find-middle, returning the wrong middle in even-length lists: slow lands on the second middle when fast starts at head, on the first middle when fast starts at head.next.
  • Forgetting to reset one pointer to head when finding cycle start; using the meeting point alone gives a node inside the cycle, not its entrance.
  • Applying the pattern to non-functional structures (multiple outgoing edges) where the math doesn't hold.

Variations

  • Cycle detection only: return boolean after slow == fast.
  • Cycle start: phase-two reset-and-walk both at speed 1.
  • Middle of linked list: single pass, no reset.
  • Functional-graph cycles: happy number, find duplicate in array of n+1 integers in 1..n.

Big O

Time
O(n)
Space
O(1)
The fast pointer traverses the list at most twice before meeting the slow pointer or reaching the end. Only two node references are kept.
Next PatternMerge Intervals