Intuition
A slow and a fast pointer meet inside the cycle. From the meeting point and from the head, two pointers advancing one step at a time meet exactly at the cycle's entrance.
Explanation
Two phases
Phase 1 — detect a meeting point. Move slow one step and fast two steps. If they ever meet, there is a cycle; if fast reaches the end, there is none.
Phase 2 — find the entrance. Let the distance from head to the cycle start be a, and the meeting point be b nodes into the cycle. The math works out so that a equals the distance from the meeting point back around to the entrance. So reset one pointer to the head and advance both one step at a time; they meet at the cycle start.
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
if slow is fast: # meeting point found
p = head
while p is not slow: p = p.next; slow = slow.next
return p # cycle entrance
return None
Worked example
[3,2,0,-4] with the tail linking back to index 1. slow and fast meet inside the cycle; resetting p to the head and stepping both lands them on the node with value 2 at index 1.
Complexity
- Time: O(n).
- Space: O(1) — only two pointers.
Implementation
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
}