Cycle detection

The problem it solves

A linked structure that is supposed to end… might not. A corrupted list whose tail points back into its body will hang every walker written for it: no null ever arrives, the loop spins forever, and nothing crashes to tell you why. Detecting that — does this list loop, and if so, where does the loop begin? — is the problem, and the constraint that makes it interesting is O(1) memory. With a hash set of visited nodes the answer is trivial (walk until you re-see a node); Floyd’s cycle detection gets the same answer with two pointer variables and nothing else, which matters when nodes number in the billions, when memory is the resource under test, or when the “list” is implicit — the iterates of a function, where storing history is the entire cost.

That last framing is why the algorithm outlives linked lists: any deterministic process x → f(x) on a finite space eventually cycles, and Floyd detects it — pseudo-random number generator periods, “happy number” loops, and the famous Find the Duplicate Number reduction, where array values are treated as pointers and the duplicate is the cycle entry. Interviews adore the technique because it looks like a trick until the two proofs land, and then it looks inevitable.

The intuition — and where it breaks down

Two runners on the track: a tortoise moving one node per tick, a hare moving two. If the track is a straight road, the hare reaches the end and the verdict is no cycle — the hare falling off is the proof, since a cycle would never have let it leave (a loop of next-pointers has no exit edge, and speed does not create one; the first prediction question exists because “it jumps over the exit” is the intuition everyone must lose).

If there is a cycle, both runners eventually orbit inside it, and here the gap argument takes over: each tick, the hare gains exactly one position on the tortoise. A gap that shrinks by exactly one, modulo the cycle length, cannot skip past zero — they do not merely “probably meet”, they must, within one lap of the tortoise entering. Watch SLOW and FAST letter themselves around the back-arc in the player and count the gap closing: the convergence proof is literally visible.

The intuition breaks down at the second question: where the runners meet is not where the cycle begins. The meeting point depends on the run-up length, and assuming it is the entry is the classic error. Phase 2 fixes it with a fact that looks like magic and is one line of algebra: restart one runner at the head, move both at speed one, and they meet exactly at the entry. The walkthrough below does the algebra; the pick-question in the player asks you to predict the meeting node before phase 2 runs.

Loading…

A walkthrough you can check

Take 8 nodes where the tail loops back to index 3 (run-up a = 3, cycle length c = 5).

1. Phase 1: tortoise and hare start at the head. Tick by tick: slow at 1, fast at 2; slow at 2, fast at 4; slow at 3 (entering the cycle), fast at 6; slow at 4, fast at 3; slow at 5, fast at 5 — met, five steps in, inside the cycle but two nodes past its entry.
2. The algebra: slow travelled a + b (run-up plus b into the cycle); fast travelled twice that. Fast’s journey is also a + b + kc (same path plus k full laps). So 2(a + b) = a + b + kc, giving a = kc − b: the run-up length equals a whole number of laps minus b.
3. Phase 2: one runner restarts at the head, a = 3 steps from the entry. The other stands at the meeting point, kc − b = 3 steps around the cycle from the entry. Both walk at speed one: three ticks later, both stand on node 3 — the entry, found without ever counting a, b, or c.

The none preset runs the other verdict: the hare hits null at full speed and the algorithm reports no cycle — absence proved, not assumed. The tight preset (two-node loop) is worth one run to see the gap argument at its most claustrophobic.

The invariant

Phase 1’s invariant: after t ticks, slow has taken t steps and fast 2t — so once both are inside the cycle, the gap (fast − slow) mod c decreases by exactly one per tick. The termination argument is that a strictly decreasing value over a finite modulus reaches zero; the meeting is forced within c ticks of slow entering the cycle, which bounds phase 1 by a + c ≤ n ticks. The no-cycle branch has its own invariant: fast is always ahead, so if any null is reachable, fast reaches it first — the tortoise never needs to check.

Phase 2’s invariant is the algebra made operational: both runners are, at every tick, equidistant from the entry — one measuring its distance down the run-up (a − t), the other around the cycle (kc − b − t, mod c). Both hit zero simultaneously; the first node they share is the entry. Note what makes this bulletproof: nothing was ever counted or stored. The distances exist in the proof, not in the program — which is the whole O(1)-space trick.

Complexity, derived

Phase 1: at most a + c ticks — the tortoise cannot enter the cycle later than tick a, and the meeting happens within one tortoise-lap after. Phase 2: exactly a ticks. Total O(n) time with small constants (two or three pointer dereferences per tick), and O(1) space: two pointers in phase 1, two in phase 2, zero auxiliary structure.

The hash-set alternative is O(n) time and O(n) space, with a bigger constant (hashing per node) but a simpler proof. The honest engineering statement: use the set when memory is plentiful and the code will be read by tired people; use Floyd when memory is the constraint, when nodes cannot be marked or stored (immutable structures, implicit graphs), or when the interviewer says O(1) space and watches your eyes. Brent’s algorithm — a teleporting variant of the hare — beats Floyd’s constant by roughly a third and is worth naming, rarely worth deriving live.

What people get wrong

• Checking equality before moving: both runners start at the head, so a pre-move check “detects” a cycle in every list, instantly. Move first, then compare — the trace’s compares happen strictly after the hops.
• Null-unsafe double hop: fast.next.next explodes when fast.next is null. The loop guard must check both, in order.
• Meeting point = entry: it is not, except by coincidence. Phase 2 exists because of this; skipping it and returning the meeting node passes exactly the test cases where a happens to be 0.
• Restarting the wrong runner in phase 2, or moving them at different speeds — the theorem is specifically head-restart, both at speed one.
• Missing the reduction: Find the Duplicate Number is this algorithm on i → nums[i]; candidates who know Floyd but cannot see the reduction lose the hard version of the question.

Implementation notes

The loop is eight lines and the displayed sources keep all three languages line-matched. Points of craft: guard with fast != null && fast.next != null (that exact order); compare references, not values — two distinct nodes may hold equal values, and == on values is a latent bug the type system will not catch in most languages; and return the entry node, not its index — callers of a list API do not have indexes.

Cycle length, if needed, falls out free: after the phase-1 meeting, hold one runner and walk the other around once, counting until it returns — exactly c ticks. Cycle removal: walk from the entry around to the node whose next is the entry, and null it — phase 2 plus one lap.

The function-iteration form deserves its own paragraph in your head: replace node.next with f(x) and Floyd detects the period of any iterated function on finite space — no list required. That is how it appears in Pollard’s rho factorisation and in PRNG analysis, and mentioning either, once, is the kind of breadth interviews remember.

The follow-up questions

Why must the runners meet rather than leapfrog? The gap changes by exactly one per tick (mod c) — a unit-step walk cannot cross zero without landing on it. “Probably meet” undersells it; the meeting is arithmetic, not luck.

Why does phase 2 land on the entry? 2(a+b) = a+b+kc gives a = kc − b: the head-runner’s distance to the entry equals the meeting-runner’s distance around to it. Equidistant, same speed, same arrival.

Why not a hash set? It is fine — O(n) memory buys a simpler proof. Floyd is for the O(1)-space constraint and for structures you cannot store or mark. Say the trade-off, then pick.

Where else does this run? Duplicate-finding via value-as-pointer, happy-number loops, PRNG period detection, Pollard’s rho. Any deterministic x → f(x) on a finite space cycles, and the tortoise and hare will find it.