Fast & slow pointers (cycle detection)
📖 Walk me through it — plain English
A linked list is a chain of boxes (called nodes); each box holds a value and an arrow (.next) pointing to the next box. Normally the last box points to None (nothing), meaning "the chain ends here." But a buggy list can have its last box point back to an earlier box — that makes a loop you'd circle forever. A cycle is exactly that loop. Our job: find out if one exists, and if so, find the box where the loop re-enters.
The trick is two walkers moving through the chain at different speeds: slow (the tortoise) hops 1 box per step, fast (the hare) hops 2. Picture a circular running track: the fast runner laps the slow one and, from behind, taps them on the shoulder — they're on the same spot. If instead the track is a dead-end straight line, the fast runner just runs off the end (fast becomes None) and we know there's no loop. Because fast gains exactly 1 box on slow every step, once both are inside a loop the gap between them shrinks by exactly 1 each step until it reaches 0 — a collision is guaranteed. No need to remember every box we've seen (a "seen-set"), so we use only two variables: that's the O(1) space payoff.
Let's trace the classic example. Four boxes — values 3 → 2 → 0 → -4 — but the last box's arrow points back to the 2, so 2 → 0 → -4 → 2 → ... loops forever. The loop re-enters at the box holding 2, so that's the answer we're hunting. Below, accent marks where slow sits and the captions spell out where fast lands.
Why does resetting to the head magically land on the entry? Call a the distance from head to the entry, and let the meeting happen b steps into the loop. A little algebra (in the box above the code) shows that the head-to-entry distance equals the meeting-point-to-entry distance, once you account for whole laps. So two walkers — one from the head, one from the meeting point — moving at the same 1-step pace must arrive at the entry together. The catch to remember: in Phase 2 fast slows down to +1 per step; keeping it at +2 is a classic bug.
Total work is O(n) time (each pointer walks a bounded number of boxes — proportional to the list length n) and O(1) space (only the two pointer variables, no growing set). The same idea solves Happy Number and Find the Duplicate, because any rule of the form x = f(x) repeatedly applied traces a chain that must eventually loop — the exact thing fast/slow is built to catch.
Imagine two runners on a track. One jogs, the other sprints at exactly double the speed. If the track is a straight line, the sprinter simply reaches the end and it is over. But if the track loops, the sprinter keeps lapping and must eventually catch the jogger from behind — they collide. That is the entire idea behind Floyd's tortoise-and-hare: walk slow by 1 and fast by 2. If fast ever runs off the end (hits None), there is no cycle; if slow and fast ever land on the same node, there is one. The gap between them shrinks by exactly 1 each step inside the loop, so a meeting is guaranteed — no hash set of seen nodes required, which is what buys you O(1) space.
The second trick is the surprising part: once they meet, you can find where the cycle begins. Reset one pointer to the head, then advance both by 1 step at a time; they meet again precisely at the cycle's entry node. The reason is a clean distance equation (spelled out below). And the whole pattern generalizes beyond linked lists: any process of the form x = f(x) traces a path that must eventually repeat, so Happy Number and Find the Duplicate Number are secretly the same problem — find a cycle in a sequence of function iterations.
- "Does this linked list have a cycle?"
- "Return the node where the cycle begins"
- O(1) space demanded — you may NOT use a seen-set
- A sequence defined by repeatedly applying x = f(x)
- You cannot modify the input (rules out cyclic-sort)
- Linked List Cycle I — detect (yes/no)
- Linked List Cycle II — return the entry node
- Happy Number — loop on sum-of-squared-digits
- Find the Duplicate Number — array as graph i -> nums[i]
- Find the midpoint of a list (fast travels 2x)
def detect_cycle(head):
slow = fast = head
while fast and fast.next: # both null checks matter
slow = slow.next # tortoise: +1
fast = fast.next.next # hare: +2
if slow is fast: # they collided -> a cycle exists
slow = head # reset one pointer to the head
while slow is not fast:
slow = slow.next # now BOTH advance by 1
fast = fast.next
return slow # the cycle's entry node
return None # hare hit the end -> no cycle
def is_happy(n):
def f(x): # sum of squared digits
s = 0
while x:
x, d = divmod(x, 10)
s += d * d
return s
slow = fast = n
while True:
slow = f(slow) # +1 application
fast = f(f(fast)) # +2 applications
if fast == 1: return True
if slow == fast: return False # looped without reaching 1
def find_duplicate(nums): # graph: i -> nums[i]
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast: break
slow = nums[0] # reset, then march by 1
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow # the repeated value// detect a cycle and return its entry node (Cycle II)
function detectCycle(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast && fast.next) { // guard fast AND fast.next
slow = slow!.next; // +1
fast = fast.next.next; // +2
if (slow === fast) { // collision -> cycle exists
slow = head; // reset one to head
while (slow !== fast) { // both step by 1
slow = slow!.next;
fast = fast!.next;
}
return slow; // entry node
}
}
return null; // no cycle
}Let a = distance from head to the entry, b = entry to the meeting point, and c = the rest of the loop back to the entry (loop length = b + c). At the meeting, slow walked a + b and fast walked twice that, so 2(a + b) = a + b + k(b + c) for some k >= 1. Simplify: a = (k - 1)(b + c) + c. In words, the distance from the head to the entry equals the distance from the meeting point to the entry (mod loop length). So once you reset one pointer to the head and step both by 1, they cover that same distance and reunite exactly at the entry.
- O(n) time, O(1) space — no seen-set; just two pointers.
- Null checks are both needed: loop on fast and fast.next so fast.next.next never dereferences None.
- Compare identity, not value: use is in Python / === in TS on the node objects.
- Phase 2 advances both pointers by 1 — not 2. A common bug is keeping the 2x speed.
- DISTINCT from cyclic-sort: that rearranges values 1..n in place. Reach for fast/slow when the input is a linked structure or you must not modify it (e.g. Find the Duplicate as a read-only array).
- Find the Duplicate needs values in [1, n] with one repeat so index 0 is never a target — that is what makes i -> nums[i] a graph with a cycle entrance.
Detect a cycle with Floyd's tortoise and hare — run it live: