In tortoise-and-hare cycle detection, why can't the fast reference skip past the slow one?

## The frame that makes the argument trivial Once **both** references are inside the loop, stop tracking their absolute positions and track only the **gap**: how many nodes the fast reference is ahead of the slow one, measured forward around the loop. Because the loop is finite and closed, that gap is a number in `0 .. C-1`, where `C` is the loop length. Each step, the slow reference advances one node and the fast one advances two. The gap therefore changes by `2 - 1 = 1` per step: **the fast reference closes on the slow one by exactly one node, every step.** A quantity that starts somewhere in `0 .. C-1` and decreases by exactly one each step must pass through zero. It cannot step from a gap of one to a gap of "minus one", because the next value after one *is* zero. Zero gap means both references are on the same node — a collision. This is the whole proof, and it is what the "could the fast one jump over the slow one?" objection misses. Skipping over would require the gap to change by two or more per step. It changes by exactly one, because the *relative* speed of a two-hop walker with respect to a one-hop walker is one hop. ## How long it takes The slow reference enters the loop after `L` steps, where `L` is the tail length. At that moment the fast reference is already somewhere in the loop, at some gap `d` with `0 <= d <= C-1`. The countdown then takes `d` more steps, so the collision happens **fewer than `C` steps after the slow reference enters the loop**. Total work is `O(L + C)`, which is `O(n)` — with a constant factor of about three node hops per element, since the fast reference covers twice the distance the slow one does. Note what the bound does *not* depend on: the payloads, the ordering, or any prior knowledge of `L`, `C`, or the total node count. The tail length decides *when* the countdown starts, not how long it lasts. ## Where the collision lands The collision node is *not* the loop entry in general. It is simply the node at which the countdown reached zero, which depends on both `L` and `C`. Treating the collision node as the entry is the single most common error in this area, and an interviewer will usually probe it immediately after you finish the meeting argument. ## Does the ratio have to be 1 and 2? Detection itself is robust: when both references start at the head, other speed pairs also collide. What is fragile is everything built *on top of* the collision. The neat "reset one reference to the head and advance both by one" trick for locating the loop entry depends on the fast reference having travelled exactly twice the slow one's distance; change the ratio and that arithmetic no longer holds in general, and you have to redo the algebra. A larger stride also burns more link traversals per step for no asymptotic gain, and complicates the end-of-list guard (a three-hop walker must check three links). One and two is the pair worth memorising, and "because the relative speed is exactly one" is the reason worth being able to say. ## The guard, and why it is not decoration ``` while fast != END and fast.next != END: slow = slow.next fast = fast.next.next ``` The double hop dereferences two links. On an acyclic list, either the fast reference itself or its immediate successor can be the end, so both must be tested before the hop. Testing only the first is a boundary bug that shows up exactly on the *acyclic* inputs — the ones a quick test with a hand-built cycle never exercises. Inside a genuine cycle neither test ever fires, which is precisely why the loop runs until the collision instead of terminating. ## Saying it in an interview "Once both are in the loop, look at the gap between them. The fast one gains one node per step, so the gap counts down one at a time and has to hit zero — it can't leapfrog, because leapfrogging would need a jump of two. The slow one enters the loop after the tail, and from there it takes fewer than a full lap, so the whole thing is linear in the number of nodes with constant extra space." That is thirty seconds, and it answers the question that was actually asked.