Fast & Slow Pointers
A runner twice as fast laps you only if there's a loop.
- Brute force
- O(n) time, O(n) space — hash set of visited nodes
- With the pattern
- O(n) — fast laps slow within one cycle length
- Extra space
- O(1)
In plain English
“Two runners on a track, one twice as fast. On a straight road the fast one simply finishes first; on a circular track the fast one eventually comes up behind the slow one and taps them on the shoulder. Whether they ever meet tells you whether the track loops.”
Why it's fast
Brute force remembers every visited node in a set (O(n) memory). With two pointers at speeds 1 and 2, once both are in the cycle the gap shrinks by one each step, so they must meet within one lap — O(1) memory. The same speed trick finds the middle (fast hits the end when slow is halfway) and, with a reset, the cycle entrance.
Spot it when the problem says…
- linked list has a cycle
- find where the cycle begins
- middle of the linked list
- O(1) extra space
- repeated process ends in a loop (happy number)
- array values in range 1..n used as next pointers
Visualize
Floyd's cycle detection
Does this linked list loop back on itself? Use O(1) extra memory.
Both runners start at the head. Slow takes 1 step per turn, fast takes 2.
1def has_cycle(head):2 slow = fast = head3 while fast and fast.next:4 slow = slow.next # 1 step5 fast = fast.next.next # 2 steps6 if slow is fast:7 return True # they met inside the loop8 return Falsevariables
- slow
- 0
- fast
- 0
How to apply it
- 01Start
slow = fast = head. - 02Loop while
fast and fast.next: move slow one step, fast two steps. - 03If they meet, there's a cycle; if fast falls off the end, there isn't.
- 04For the cycle start: reset one pointer to head and move both one step until they meet.
Variations you'll meet
Cycle detection (Floyd)
The visualizer's example.
def has_cycle(head) -> bool: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return FalseCycle entrance
Distance from head to entrance equals distance from meeting point to entrance (mod cycle length).
def detect_cycle(head): slow = fast = head while fast and fast.next: slow, fast = slow.next, fast.next.next if slow is fast: slow = head while slow is not fast: slow, fast = slow.next, fast.next return slow return NoneFind the middle
When fast reaches the end, slow is at the middle — the setup for Palindrome List and Reorder List.
Implicit linked list
Find the Duplicate Number: treat i -> nums[i] as a next pointer; the duplicate is the cycle entrance.
Common mistakes
- Checking
fast.next.nextwithout first checkingfast.next→ AttributeError on None. - Comparing values (
==) instead of node identity (is). - Checking
slow is fastbefore moving them, so they 'meet' at head immediately. - Off-by-one for even-length lists: decide whether you want the first or second middle.
Practice ladder
Easy → hard. Tick them off as you go.
Think you've got it?
Let the AI interviewer throw a Fast & Slow Pointers problem at you and grade how you explain it.