Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
Example 1
Input: head = [3,2,0,-4], pos = 1 (tail connects to index 1)
Output: node with value 2
Explanation: The cycle begins at the node with value 2.
Example 2
Input: head = [1], pos = -1
Output: null
Explanation: No cycle.
The number of nodes is in the range [0, 10^4]-10^5 <= Node.val <= 10^5First detect whether a cycle exists at all using Floyd's slow/fast pointer technique — the same approach as the basic cycle-detection problem.
The interesting part is what happens after slow and fast meet inside the cycle: that meeting point isn't the cycle's start, but it has an exact mathematical relationship to it.
Try resetting one pointer to head and moving both remaining pointers one step at a time — where do they meet?
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) { // cycle confirmed — now find its start
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null; // fast reached the end — no cycle
}Time: O(n) · Space: O(1)