Fast and Slow Pointers

1. The signal

Use two pointers moving through the same deterministic next relation when the question asks for:

• a cycle or its entrance;
• the middle of a list;
• the nth node from the end;
• two positions separated by a fixed distance;
• a duplicate in an array whose values can be treated as next indices.

The pattern is about relative movement, not specifically linked-list syntax.

2. Middle template

ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow is at the middle (the second middle for even length)

let slow = head, fast = head;
while (fast && fast.next) {
  slow = slow.next;
  fast = fast.next.next;
}

After t iterations, slow has moved t edges and fast 2t. When fast reaches the end, slow has covered half the distance. Reorder List adjusts the loop condition to stop slow at the end of the first half, which makes splitting easier.

3. Cycle-detection template

ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;
}
return false;

let slow = head, fast = head;
while (fast?.next) {
  slow = slow.next;
  fast = fast.next.next;
  if (slow === fast) return true;
}
return false;

Compare node identity, not values. Two different nodes may store the same value.

Why the meeting is guaranteed

If there is no cycle, fast reaches null. If there is a cycle, both pointers eventually enter it. Inside the cycle, fast gains one position per iteration. On a loop of length C, the relative distance becomes d, d+1, d+2, ... (mod C) and must hit zero.

4. Finding the cycle entrance

After the first meeting:

1. keep one pointer at the meeting point;
2. put another at the head;
3. move both one edge at a time;
4. their next meeting is the entrance.

This powers Find the Duplicate Number. Index i is an implicit node and nums[i] is its next pointer. The repeated value is where two incoming paths merge—the entrance of the cycle.

5. Fixed-gap template

Different speeds are not always needed. For “nth from end,” preserve a gap:

ListNode dummy(0, head);
ListNode *slow = &dummy, *fast = &dummy;
for (int i = 0; i <= n; ++i) fast = fast->next;
while (fast) {
    slow = slow->next;
    fast = fast->next;
}
// slow->next is the target

The extra one edge places slow before the target, which is the position deletion requires. Starting at a dummy makes removing the original head work without a separate case.

6. Complexity

All variants use O(n) time and O(1) auxiliary space. A pointer may traverse the list twice as fast, but 2n is still O(n). No visited set is needed for Floyd’s cycle algorithm.

7. Traps

• Moving fast two edges without first proving both edges exist.
• Checking equality before either pointer moves; they start equal by construction.
• Returning the first meeting as the cycle entrance—it is generally only an interior point.
• Using values instead of reference identity.
• Mixing the middle loop conditions. Decide whether you need the second middle or the end of the first half, then hand-trace even lengths.

Blank practice

Draw a list with a five-node prefix and a four-node cycle. Record slow and fast after every move. Then reset one pointer and locate the entrance. Finally repeat with no cycle and explain exactly which null check terminates the loop.