In tortoise-and-hare cycle detection, how do you locate the cycle's entry node after the collision?
answer
- the collision node is not the entry
- name the three distances first
- tail length, lap length, offset past entry
- the fast one covered exactly double
- whole laps cancel out
basics
~20 sLeave one reference on the collision node, move the other back to the head, then advance both a single node per step. They meet exactly on the cycle's first node, because the head-to-entry distance and the collision-to-entry distance differ only by whole laps.
solid answer
~50 sName three distances: `L` from the head to the entry, `C` for the loop length, and `m` for how far past the entry the collision happened. The slow reference travelled `L + m`; the fast one travelled twice that and stands on the same node, so `2(L + m) = (L + m) + kC`, giving `L + m = kC`, that is `L = kC - m`. So walking `L` steps from the head lands on the entry, and walking the same `L` steps forward from the collision node lands `m + kC - m = kC` past the entry — whole laps, which is the entry again. The procedure is therefore: reset one reference to the head, keep the other at the collision, advance **both by one**, and stop where they coincide. That costs `O(L)` extra steps and no extra memory, and note the collision node itself is not the entry.
code
pseudocode · 7 lines// entering here, meet is the collision node inside the cycle
p = head
q = meet
while p != q:
p = p.next
q = q.next
return p // the cycle's entry nodego deeper
Recall the recipe: after the collision, move one reference back to the head, then step both one node at a time until they meet, and that meeting point is where the loop begins.
Derive it, do not recite it. Define the tail length, loop length and offset past the entry, show that double distance forces their sum to be a whole number of laps, and conclude that the laps cancel.
Show judgment about the edges: the head-inside-the-loop case, a tail far longer than the loop, and the fact that the identity depends on the two-to-one ratio, so a 'faster is better' tweak silently breaks the second phase.
Own the call of whether a hand-derived proof belongs in production code at all — what the tests must pin down, what the comment must record, and when a validated library routine is the responsible choice over clever arithmetic nobody on the team can re-derive.
## The three distances Name them before you reason, because the proof is one line once they exist: - `L` — the number of hops from the head to the **entry**, the first node of the loop. - `C` — the **loop length**, the number of nodes on the cycle. - `m` — how far **past the entry**, measured forward around the loop, the two references collided (`0 <= m < C`). Note first that the collision node is generally *not* the entry. `m` is whatever it happens to be; it depends on `L` and `C`. ## The algebra The slow reference took `L + m` hops to reach the collision node: `L` to reach the entry and `m` more around the loop. (It cannot have lapped: it enters the loop after `L` steps and, since the gap closes by one per step and starts below `C`, it collides within a further `C` steps.) The fast reference took exactly twice as many hops, `2(L + m)`. It also stands on the collision node, so its distance must be the slow one's distance plus a whole number of laps: ``` 2(L + m) = (L + m) + k*C for some integer k >= 1 ``` Subtract `L + m` from both sides: ``` L + m = k*C -> L = k*C - m ``` That identity is the entire trick. It says: **the distance from the head to the entry equals the distance from the collision node forward to the entry, plus some whole laps** — and whole laps are invisible to a walker circling the loop. ## The procedure that falls out of it Leave one reference on the collision node. Move the other back to the head. Now advance **both by one node per step**, and compare them each step. - After `L` steps, the head-side reference stands exactly on the entry. - After `L` steps, the loop-side reference has moved `L = k*C - m` nodes forward from a position `m` past the entry, putting it `m + k*C - m = k*C` past the entry — that is `k` complete laps, which is the entry itself. They are on the same node, and that node is the entry. The walk costs `O(L)` steps and no extra memory, so the two phases together are still `O(n)` time and `O(1)` space. ## A worked example Tail `L = 3`, loop `C = 6`. The slow reference enters the loop at step 3; the fast one is then at hop 6, which is 3 nodes into the loop, so the gap is 3. The gap closes by one per step, so they collide 3 steps later: slow at hop 6 (offset 3 into the loop), fast at hop 12 (offset `(12-3) mod 6 = 3`). So `m = 3`, and indeed `L + m = 6 = 1 * C`. Phase two: the head-side reference walks 3 hops to the entry; the loop-side one walks 3 hops from offset 3 to offset 6, which wraps to offset 0 — the entry. Both land together, as promised. ## Edge cases the proof already covers - **`L = 0`** (the head is inside the loop): then `m` must satisfy `m = k*C`, i.e. `m = 0`, so the collision *is* the head. Phase two compares the two references before moving anything and stops immediately at the head. No special case needed. - **`C = 1`** (a self-link): the collision is on that node, and phase two walks the head-side reference to it. - **Tail longer than the loop** (`L > C`): nothing changes; `k` is simply larger than one. Candidates sometimes claim the proof needs `L < C` — it does not, because the laps cancel for any `k`. ## Two things that break it **Changing the speed ratio.** With a three-hop fast reference the relation becomes `3(L+m) = (L+m) + k*C`, i.e. `2(L+m) = k*C`, and `L = k*C/2 - m` is not the identity the reset relies on. Detection still works; the reset does not, in general. **Assuming the collision node means something on its own.** It does not. Its only role is to give you a point whose distance to the entry, going forward, is congruent to `-L` around the loop. ## Related measurement: how long is the loop? Once you have a collision node, loop length falls out for free: freeze one reference on it, walk the other one node at a time, and count the hops until it comes back to the frozen one. That count is `C`, in `O(C)` time and constant space. This is worth knowing because it also gives an alternative entry-finding route — put one reference `C` hops ahead of another at the head and advance both together — but the reset-to-head form is shorter and needs no counting.
- How would you measure the length of the cycle once you have a collision node?Freeze one reference on the collision node and walk a second one forward, counting hops until it returns to the frozen node. That count is the loop length, in `O(C)` time and constant space. No prior knowledge of the chain's total length is needed — a common misconception is that these techniques require the length up front, and none of them do.
- What does the second phase do when the cycle starts at the head node itself?It stops immediately. With `L = 0` the identity `L + m = kC` forces `m` to be zero, so the collision node *is* the head, and the two references are already equal before either moves. The general procedure handles it with no special case, which is worth stating rather than adding a branch.
- Does the proof require the tail to be shorter than the cycle?No. The relation `L = kC - m` holds for any positive integer `k`, so a tail many laps longer than the loop is fine — the head-side reference simply walks further while the loop-side one makes more complete laps. Assuming `L < C` is a common misreading that makes candidates doubt a correct algorithm.
saying these in an interview costs you the question
- Calls the collision node the start of the cycle
- Claims you must know the list length first
- Keeps the two-to-one speeds during the second phase
- Says the proof needs the tail shorter than the loop
- Believes locating the entry requires storing visited nodes