Fast & Slow Pointers
The Intuition
Two runners on a track. One runs at normal speed, the other at double speed. If the track is a straight line, the fast runner reaches the finish while the slow runner is only halfway. That's your middle-finding trick right there: when fast hits the end, slow is at the midpoint.
Now imagine the track loops back on itself. The fast runner doesn't hit an end because there is no end. Instead, the fast runner keeps lapping around and eventually catches up to the slow runner from behind. They collide. That collision proves there's a cycle. If the fast runner had reached a dead end instead, you'd know the track is straight with no loop.
But here's the really clever part. After they meet inside the cycle, how do you find where the loop starts? Reset the slow runner back to the starting line. Now both runners move at the same speed, one step at a time. They'll meet again, and the spot where they meet is exactly the entrance to the cycle. It feels like a magic trick, but it falls out of the math. The distance from the start to the cycle entrance equals the distance from the meeting point to the cycle entrance (going around the loop). So both runners cover the same distance and arrive together.
You get cycle detection, cycle start location, and middle-finding all from the same two-pointer idea. No extra data structures. No hash sets. Just two pointers moving at different speeds, and the geometry of the structure tells you everything.
Cycle detection in linked lists, finding the middle node, detecting the start of a cycle, checking if a linked list is a palindrome (combined with reversal), or happy number problems.
- Need to detect cycles in directed graphs (use DFS coloring)
- Need cycle length immediately (fast-slow finds start, not length directly)
- Array-based problems without pointer semantics
Variations:
- Cycle detection: Determine if a cycle exists.
- Cycle start: After meeting, reset one pointer to find where the cycle begins.
- Middle finding: When fast reaches the end, slow is at the middle.
- single node
- no cycle
- cycle at head
Key Points
- •Slow moves 1 step, fast moves 2 steps per iteration
- •If there's a cycle, fast and slow will meet
- •When fast reaches end, slow is at the middle
- •To find cycle start: reset one pointer to head after meeting
- •Also known as Floyd's Tortoise and Hare algorithm
Code Template
1 def has_cycle(head):
2 """Detect if linked list has a cycle."""
3 slow = fast = head
4 while fast and fast.next:
5 slow = slow.next
6 fast = fast.next.next
7 if slow == fast:
8 return True
9 return False
10
11 def find_cycle_start(head):
12 """Find the node where the cycle begins."""
13 slow = fast = head
14 while fast and fast.next:
15 slow = slow.next
16 fast = fast.next.next
17 if slow == fast:
18 slow = head
19 while slow != fast:
20 slow = slow.next
21 fast = fast.next
22 return slow
23 return None
24
25 def find_middle(head):
26 """Find the middle node of the linked list."""
27 slow = fast = head
28 while fast and fast.next:
29 slow = slow.next
30 fast = fast.next.next
31 return slowCommon Mistakes
- Not checking fast and fast.next for null before advancing
- Confusing the cycle detection with cycle start detection
- Forgetting that for even-length lists, slow stops at the second middle