Fast & Slow Pointers
Two pointers at different speeds. Fast catches slow if a cycle exists. Slow lands on the middle when fast hits the end. O(1) space, O(n) time — no HashSet needed.
Detect a cycle using a HashSet — O(n) space. Using fast/slow — O(1) space
The insight: two runners on a circular track always meet. Fast (2 steps) gains exactly 1 step on slow (1 step) per iteration. The gap closes by 1 each time — it must reach 0. They meet inside the cycle, proving it exists. No storage needed.
Two Uses of Fast & Slow
Every fast/slow problem is one of these two. Identify before coding.
Fast pointer catches slow inside a cycle. If fast hits null, no cycle. If they meet, cycle confirmed. Two-phase variant finds exact cycle start.
When fast reaches end (null or last node), slow is exactly at the middle. Use to split a list, find middle for palindrome check, or restructure.
The 3-Step Framework
The same template works for every fast/slow problem.
Both slow and fast start at head (not head.next). The loop condition checks 'fast and fast.next' — both must be non-null before attempting fast.next.next.
slow, fast = head, head while fast and fast.next:
slow = slow.next (1 step). fast = fast.next.next (2 steps). For cycle detection: check 'slow is fast' after advancing. For middle: just advance, no check needed.
slow = slow.next fast = fast.next.next if slow is fast: # cycle!
After meeting point is found: reset slow to head, keep fast at meeting point. Advance both 1 step at a time. Where they meet again is the cycle start — mathematical proof guarantees it.
slow = head # reset
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # cycle startRecognition
Fast/Slow vs other pointer patterns — choose correctly in 20 seconds.