142. Linked List Cycle II
Once more you receive head of a singly linked list that may loop: the tail's next pointer either is null or has been wired back to some earlier node. Detection alone is no longer enough — return the exact node where the cycle begins, or null when the list has no cycle. Do not modify the list.
The judge takes the node your function returns and prints its 0-based position in the original list (or -1 when you return null), so the answer is fully determined.
As before, the test input describes the wiring with an integer pos (the index the tail links back to, -1 for none), but your function is only ever handed head.
The follow-up worth chasing: find the entry node using O(1) extra memory.
Example 1:
Input: head = [3, 2, 0, -4], pos = 1
Output: the node at index 1 (value 2)
Explanation: The tail (value -4) connects back to the node at index 1 (value 2), so that node is where the cycle starts.
Example 2:
Input: head = [1, 2], pos = 0
Output: the node at index 0 (value 1)
Explanation: The second node links back to the first, so the cycle begins at the head itself, index 0.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
- pos is -1 or a valid 0-based index into the list
Hints:
The hash-set idea from cycle detection already solves this: walking from head, the first node you meet for a second time is precisely the cycle's entry — no node before it is ever revisited.
For O(1) space, run the slow/fast race until the pointers collide somewhere inside the loop. Now restart one pointer at head and advance both one step at a time: they meet exactly at the cycle entry. Prove it by writing the fast pointer's distance as twice the slow pointer's — the head-to-entry distance a and the meeting point's position b inside the loop satisfy a ≡ (c − b) mod c, where c is the cycle length.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [3, 2, 0, -4], pos = 1
Expected output: 1 (the node with value 2)