Fast/Slow & Gap Pointers

A singly linked list only lets you walk forward, and you usually don't know its length. Two pointers get around both limits without extra memory. Move them at different speeds (slow 1 step, fast 2 steps) to detect a loop or find the middle. Move them at the same speed with a fixed gap to find the k-th node from the end in one pass.

The idea#

A linked list has no index, so you cannot jump to the middle or count back from the end. Two pointers that move at different speeds, or stay a fixed distance apart, give you that position in one pass.

Tortoise and hare#

• Cycle detection: if the list has a loop, fast eventually laps slow and they land on the same node. If there is no loop, fast reaches None.
• Middle: fast covers twice the distance, so when fast reaches the end, slow is halfway.

Why must they meet? Once both pointers are inside the loop, measure the distance from fast forward to slow. Each step slow moves 1 and fast moves 2, so the gap shrinks by exactly 1. It can't jump over zero, so they meet. The gap starts below the loop length, so this takes at most one lap after slow enters: $O(n)$ overall, $O(1)$ space.

Finding where the cycle starts (Floyd)#

Knowing there is a loop is often only half the job. The meeting point is not in general where the loop starts. To find the entry, reset one pointer to head and move both one step at a time. Where they meet now is the entry.

Why does this work? Let a be the steps from head to the entry, b the steps from the entry to the meeting point, and c the loop length.

1. When they meet, slow has walked a + b and fast has walked 2(a + b).
2. Fast's extra distance, a + b, was spent going around the loop, so it is a whole number of laps: a + b = k * c.
3. So a = k * c - b. Starting at the meeting point (which is b past the entry), walking a steps means walking k * c - b. That lands exactly on the entry.
4. A pointer starting at head also reaches the entry after a steps. Both arrive together.

Gap pointers#

The second setup keeps both pointers at the same speed and changes only where they start. To find the k-th node from the end, give right a head start of k nodes, then move both together. When right falls off the end, left is k nodes behind it. Start left at a dummy node and it stops just before the target, which is what you need to delete it.

How to spot it#

Each signal maps to one pointer setup.

• "Is there a loop?", "where does the loop start?": fast and slow.
• "Find the middle", "split the list in half": fast and slow.
• "k-th node from the end", "remove the n-th from the end": gap pointers. Move right first, then both.
• "Where do two lists meet?": align the two pointers so they have the same distance left.
• An array whose values are valid indices (i -> nums[i]) behaves like a linked list, so cycle tricks apply.

Template#

This is Floyd's cycle detection with the entry point. Both pointers must start at head for the a + b argument to hold.

slow = head
fast = head
while fast is not None and fast.next is not None:
    slow moves 1 step; fast moves 2 steps
    if slow is fast:                 # phase 1: there is a cycle
        slow = head                  # phase 2: reset one pointer
        while slow is not fast:
            slow moves 1 step; fast moves 1 step
        return slow                  # they meet at the entry
return None                          # fast fell off: no cycle

Gap pointers shape#

The gap version from the idea above walks one pointer ahead, then moves both at the same speed.

dummy = new node whose next is head
left = dummy
right = head
repeat k times: right = right.next   # right gets a k-node head start
while right is not None:
    left = left.next; right = right.next
left now sits just before the k-th node from the end

Which middle?#

Finding the middle uses the same fast and slow loop, but an even-length list has two middles. The start position of fast decides which one you get.

Use the first-middle version when you split a list for merge sort: a two-node list then splits 1 + 1 (see Merging & Sorting Lists).

Pitfalls#

These mistakes cause most wrong answers and infinite loops.

• Thinking the meeting point is the loop start. It is only where fast caught slow. The entry needs the reset-and-walk phase.
• Starting fast one step ahead for Floyd. fast = head.next is fine for detecting a cycle. It breaks the a + b bookkeeping, though, and phase 2 can loop forever. Start both at head when you need the entry.
• Checking fast.next.next without checking fast.next. The loop condition must be fast and fast.next.
• Comparing values instead of nodes. Use is for node identity; different nodes can hold equal values.
• Gap off by one. Starting left at dummy (not head) leaves it before the target, ready to unlink.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

• 141. Linked List Cycle
• 876. Middle of the Linked List
• 160. Intersection of Two Linked Lists
• 142. Linked List Cycle II
• 19. Remove Nth Node From End of List
• 1721. Swapping Nodes in a Linked List
• 287. Find the Duplicate Number

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Different speeds: loops and middles. Same speed with a gap: k-th from the end.
• Inside a loop the gap shrinks by one per step, so fast always catches slow in $O(n)$.
• The meeting point is not the entry; reset one pointer to head and walk both one step at a time.
• Start gap pointers from a dummy so the left one stops before the node to delete.
• Compare nodes with is, not by value.