Linked List Cycle II
Given a linked list, return the node where the cycle begins — not just whether one exists. Return null if there is no cycle. O(1) memory required.
Intuition
Run the slow/fast race until they meet inside the loop. Then the magic: reset one pointer to the head and walk both one step at a time — they collide exactly at the cycle's entrance. The distances cancel out perfectly.
Approach
Phase 1 — detect with slow/fast
Same as Cycle I: slow moves 1, fast moves 2. If fast falls off the end there's no cycle → null. If they meet, a cycle exists and the meeting point is somewhere inside it.
Phase 2 — the distance cancellation
Call the head→entry distance a, entry→meeting b, and the cycle length c. When they meet, fast has walked exactly twice slow's distance: a + b + kc = 2(a + b), which simplifies to a = c − b (mod c). Translation: from the meeting point, the entry is exactly a steps ahead — the same distance as from the head.
Walk both ×1 and collide at the entry
So reset slow to the head, keep fast at the meeting point, and advance both one step at a time. After a steps they are both standing on the cycle's first node — return it. No counting, no hashing, O(1) space.
Solution & live demo
Edge cases
Fast (or fast.next) hits null in phase 1 — return null before phase 2 ever runs.
a = 0: phase 2's loop condition is false immediately and the head itself is returned.
The meeting can happen anywhere in the loop; the cancellation argument doesn't care — phase 2 still lands on the entry.