The site's other ten Graph Traversal entries all visit a
graph with an explicit stack or queue and a visited set, spending O(V) memory to
remember where they've been. This entry answers one narrow question — does a linked list (or any
structure where each node points to exactly one next node, a functional graph)
loop back on itself, and if so, at which node does the loop begin — using two pointers walking the
same path at different speeds and no memory of the past at all. It's the mechanism
Pollard's Rho borrows to detect a collision in
a pseudorandom sequence without storing the sequence, applied here to its original, more literal
setting: a chain of nodes that may or may not loop.
A node with a cycle looks like the letter ρ (rho): a straight tail of μ nodes leading in, then a loop of λ nodes that repeats forever. The obvious way to find where the loop starts is to walk the list once, dropping every visited node into a hash set, and stop at the first node already in the set — O(n) time, O(n) space. Floyd's algorithm gets the same answer in O(n) time but O(1) space: a slow pointer (the tortoise) advances one node per step, a fast pointer (the hare) advances two, and if the list has a cycle the two are mathematically guaranteed to land on the same node before the hare has gone around the loop twice — no set required, because the hare re-visiting the tortoise's own trail inside the cycle *is* the detection.
Each box is one node, laid out in the order a walk from the head visits them. The last node's arrow either points back into the loop (cycle) or ends the list (no cycle). Step through phase 1 (find a meeting point inside the cycle) and phase 2 (find exactly where the cycle starts).
Phase 1 — a meeting point is guaranteed to exist. If the list has no cycle, the hare reaches the end (a null next-pointer) and the search reports "no cycle" — nothing to prove there. If it does have a cycle, once both pointers are inside the loop they're two runners on a circular track of length λ, the hare gaining one position on the tortoise every step. A gap that shrinks by exactly 1 each step and starts somewhere between 0 and λ-1 must hit exactly 0 within λ steps — the hare can't jump over the tortoise, since it only gains one position at a time. So they meet at some node M inside the cycle, after at most μ + λ steps of the tortoise.
Phase 2 — the meeting point, reset one way, points at the cycle start. This is
the non-obvious part. Let μ be the tail length and λ the cycle length. By the time the tortoise
first enters the cycle (after μ steps), the hare has already taken 2μ steps — it's μ steps ahead of
the tortoise along the cycle, i.e. at cycle-position (μ mod λ). From there the gap between
them (hare ahead of tortoise, measured around the cycle) shrinks by 1 per step, so they meet after
another λ − (μ mod λ) steps, at cycle-position λ − (μ mod λ) + (μ mod λ) = λ ≡
0... expressed the usual way, at a point that is exactly μ steps behind the
cycle's start, measured going forward around the loop. That's the entire trick: a pointer
starting at the list's head is, by definition, exactly μ steps from the cycle's start. A pointer
starting at the meeting point is also exactly μ steps (going around the loop) from the
cycle's start. Advance both one node at a time and they arrive at the cycle's start — the same node
— simultaneously, regardless of what μ and λ actually are. The proof never needed to know either
number; it only needed both pointers to close an identical distance at an identical speed.
function findCycleStart(head) {
let slow = head, fast = head;
// Phase 1: advance until they meet, or the hare falls off the end.
while (true) {
if (fast === null) return null;
fast = fast.next;
if (fast === null) return null;
fast = fast.next;
slow = slow.next;
if (slow === fast) break;
}
// Phase 2: one pointer restarts at head, both now advance at the same speed.
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // the node where the cycle begins
}Phase 2 only works if both pointers move at the same speed — leaving the hare at
double speed "to save time" silently returns the wrong node. The proof above relies on
both pointers closing an identical μ-step distance at an identical rate; if the hare keeps
advancing two nodes per step instead of one after the phase-2 reset, the two distances no longer
shrink in lockstep and they can meet before either one has actually reached the cycle's start.
Checked against a brute-force hash-set walk across 2,000 random tail/cycle-length combinations
(tail 0–10, cycle 1–10): the same-speed version matches the brute-force answer every time, the
hare-stays-fast version disagrees on 1,326 of 2,000 (66.3%). The smallest failing
case is tail length 1, cycle length 2 — three nodes, 0 → 1 → 2 → 1 → …. The correct
cycle start is node 1; the hare-stays-fast variant meets at node 1 first (matching the true
meeting point from phase 1) but then walks straight past it and reports node 2 instead, because by
the time the reset tortoise has taken its one step, the still-fast hare has already taken two and
overshot the actual answer.
Checking for the end of the list after the wrong hop crashes instead of reporting "no
cycle." The hare needs two null checks per phase-1 step — one after each of its two hops
— because either hop can be the one that runs off the end. A version that checks only once, after
both hops (fast = fast.next; fast = fast.next; if (fast === null) return null;),
looks almost identical to the correct code above but dereferences .next on a
null node whenever the *first* hop is the one that reaches the end. Tested against
six cycle-free lists of length 1 through 6: every single one crashes with a
TypeError: Cannot read properties of null before phase 1 ever gets the chance to
correctly report "no cycle" — not a subtle intermittent bug, a 6-for-6 failure across every length
tried.
Phase 1 takes at most μ + λ tortoise-steps to find a meeting point (the tortoise still hasn't finished its first lap of the cycle when the hare, moving twice as fast, catches back up to it from behind). Phase 2 takes at most another λ steps. Both phases are bounded by O(n) where n = μ + λ is the total number of nodes, and — the entire point of the technique — the only state kept between steps is the two pointers themselves: O(1) space, against O(n) for the hash-set walk this page opened with. Nothing about the two-pointer trick is specific to linked lists; it applies to any function that maps each state to exactly one next state (a "functional graph"), which is exactly the setting Pollard's Rho reuses it in, walking the sequence x, x²+c, (x²+c)²+c, … mod n instead of a chain of list nodes.
This site's guide, Choosing a Graph Traversal Approach, places this entry apart from every other Graph Traversal page: it's the one answer in the category that doesn't use a stack, queue, or visited set at all, because the graph it walks — every node with exactly one outgoing edge — never branches.