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.
- The number of the nodes in the list is in the range [0, 10⁴].
- -10⁵ <= Node.val <= 10⁵
- pos is -1 or a valid index in the linked-list.
Intuition
Linked list cycle ii asks not merely whether a cycle exists but where it begins — and in O(1) memory, which rules out a hash set of visited nodes.
Phase one is the familiar tortoise-and-hare race. A slow pointer moves one step, a fast pointer two. If the fast pointer reaches the end, there is no cycle. If they meet, one exists — but the meeting point is not the cycle's entrance, and that is the whole difficulty.
Phase two is where the arithmetic pays off. Call the distance from the head to the entrance a, the distance from the entrance to the meeting point b, and the cycle length c.
When they meet, slow has travelled a + b and fast has travelled exactly twice that. Fast has also gone round the loop some whole number of times, so 2(a + b) = a + b + n·c, which simplifies to a + b = n·c, and therefore:
- a = n·c − b — the distance from the head to the entrance equals the distance from the meeting point onward to the entrance, plus whole loops.
So reset one pointer to the head, leave the other at the meeting point, and advance both one step at a time. After exactly a steps they collide at the entrance — the loops the second pointer makes are complete circuits and change nothing.
That cancellation is why the trick looks like magic and is really just algebra.
The follow-up with a genuinely surprising result: after the pointers meet, reset one to the head and advance both one step at a time — they meet again exactly at the cycle's entrance. It falls out of the algebra (the distance from head to entry equals the distance from the meeting point to entry, modulo the loop length), and it's worth being able to state that rather than just memorising the move.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Race slow and fast to detect the cycle
Slow advances one node, fast two. If fast or fast.next becomes null there is no cycle — return null. Otherwise they meet somewhere inside the loop, though not at its entrance.
Understand why they must meet
Once both are inside the loop, fast gains one position on slow per step, so the gap closes by one each time and cannot be skipped over. Meeting is guaranteed within one loop length.
Do the distance algebra
With a head-to-entrance, b entrance-to-meeting and c the loop length, fast travels twice slow's distance: 2(a+b) = a+b+n·c, giving a = n·c − b. That equality is the entire justification for phase two.
Reset one pointer to the head
Leave the other at the meeting point. Advance both one step at a time — the speed change is essential, since keeping fast at double speed breaks the equality the algebra established.
Collide at the entrance
After exactly a steps both pointers stand at the cycle's entrance. The second pointer's extra whole loops are complete circuits that leave its position unchanged — which is why the meeting is exact rather than approximate.
Cost of the two phases
Both phases are linear in the list length, giving O(n) time and O(1) space. A hash set of visited nodes is easier to reason about but costs O(n) memory, which is precisely what this problem forbids.
Solution & live demo
Common pitfalls
Returning the meeting point as the entrance
if slow is fast:
return slowif slow is fast:
slow = head
while slow is not fast:
slow = slow.next; fast = fast.next
return slowThe meeting point is wherever the lap happened to complete, which is generally somewhere in the middle of the cycle rather than its entrance. The second phase is what converts one into the other.
Keeping the fast pointer at double speed in phase two
while slow is not fast:
slow = slow.next
fast = fast.next.nextwhile slow is not fast:
slow = slow.next
fast = fast.nextThe equal-distance argument only holds at matched speed. Leaving the hare at double pace makes the two pointers meet somewhere arbitrary inside the loop, or miss the entrance entirely.
Resetting the wrong pointer
fast = head
slow = head
Either works as long as the other stays at the meeting point — but resetting both, or resetting one and then advancing from the wrong start, breaks the invariant. Exactly one pointer returns to the head.
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.