Fast & Slow Pointers

How It Works

The fast & slow pointer technique (also called Floyd's cycle detection, or "the tortoise and the hare") uses two pointers that traverse the same sequence at different speeds: typically the slow pointer moves one step at a time while the fast pointer moves two. If the sequence has a cycle, the fast pointer eventually "laps" the slow pointer and they land on the same node; if the sequence terminates cleanly, the fast pointer simply reaches the end first.

The elegance of this pattern is that it needs no extra memory to track visited nodes. A hash-set approach to cycle detection works too, but costs O(n) space; fast & slow pointers solve the same problem in O(1) space by relying purely on relative speed.

Beyond cycle detection, the same two-speed idea finds the middle of a list in a single pass (when the fast pointer reaches the end, the slow pointer is at the midpoint), and, with a second phase after the pointers first meet, can pinpoint exactly where a cycle begins, not just whether one exists.

When To Use It

• The problem is about a linked list and either explicitly or implicitly involves a cycle.
• You need the middle element of a list in one pass, without first counting the length.
• A sequence of transformed values might repeat forever (e.g., repeatedly summing squared digits, as in Happy Number): treat the sequence of values as an implicit linked list and detect a cycle in it.
• The interviewer emphasizes a constant-space constraint, ruling out a visited-set approach.

Time & Space Complexity

• Time: O(n): each pointer visits at most a bounded multiple of the sequence length before either meeting or reaching the end.
• Space: O(1): only two pointers are held in memory, regardless of input size.

// Canonical fast & slow pointer cycle detection
function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // pointers met: cycle found
  }

  return false; // fast reached the end: no cycle
}

Alternative Approaches

• Hash set of visited nodes (O(n) space): straightforward and easy to reason about, but the extra memory is exactly what fast & slow pointers avoid; many interviewers explicitly ask for the constant-space version.
• Marking nodes as visited in place: works if you're allowed to mutate node structure (e.g., flipping a visited flag), but that's often disallowed or considered destructive to the input.
• Length-counting for "find the middle": traverse once to count length, then traverse again to the length / 2-th node; correct but requires two full passes instead of one.

Common Mistakes

• Null-checking only fast, not fast.next: advancing fast by two steps means you must check both fast !== null and fast.next !== null before dereferencing fast.next.next, or you'll throw on odd-vs-even length lists.
• Forgetting the second phase for "find the cycle start": detecting that a cycle exists is only half of Floyd's algorithm; finding where it starts requires resetting one pointer to the head and advancing both one step at a time until they meet again.
• Assuming "middle" means the same thing for even-length lists: with fast moving two steps per one of slow's, an even-length list lands slow on the second of the two middle nodes; confirm which convention the problem wants.
• Using this pattern where a hash set is actually required: if the problem needs you to identify which value repeats (not just that a cycle exists), you may still need auxiliary storage; don't force the pattern where it doesn't fit.

Pattern Summary

Fast & slow pointers turn cycle detection and middle-finding into a single linear pass with zero extra memory, by exploiting the simple fact that a faster pointer will either escape a finite sequence first or lap a slower one stuck in a loop. It's the default answer whenever a linked-list (or linked-list-shaped) problem calls out constant space.