Two Pointers · Fast & slow LeetCode 142

Linked List Cycle II / visualized

Two phases, and the second one is the part nobody can reconstruct from memory. Phase 1 is plain Floyd: slow steps one, fast steps two, and inside a loop they must collide. Phase 2: reset a pointer to head and advance both one step at a time — they meet at the cycle entrance. Why: let a = head→entrance, b = entrance→meeting, c = cycle length. Slow walked a+b, fast walked 2(a+b), and fast's extra a+b is a whole number of laps, so a + b = k·c → a = k·c − b. Walking a more steps from the meeting point lands exactly on the entrance.

List values (comma-separated)

Cycle entry index (−1 = none)

Execution

idle

Press Run to begin.

0 / 0

Speed

Java · running line

slow — 1 step fast — 2 steps p — restarted at head cycle entrance null / end

O(n) time · O(1) space · phase 1 finds a meeting point, which is almost never the entrance; phase 2 is what converts that meeting point into the answer, and it works because a ≡ −b (mod c).