Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. Internally, pos is the index the tail's next points to (-1 means no cycle). Do not modify the list, and use O(1) extra memory.
head = [3,2,0,-4], pos = 1node at index 1head = [1,2], pos = 0node at index 0head = [1], pos = -1null (no cycle)headnull (no cycle)head; keep 🐇 at the meeting pointWhen they meet, 🐢 has walked a + b and 🐇 has walked 2(a + b), which is also a + b + k·L (it lapped the loop k times). So a + b = k·L, i.e. a = k·L − b = (k − 1)·L + c. Walking a steps from the meeting point lands on the start. That's exactly what walking a steps from head does.
Empty list or one node without a loop → return null. Cycle starts at head (pos = 0) → they meet, and after the reset both are already on the answer. Self-loop at the tail works the same way. A HashSet solution is simpler but uses O(n) memory; interviewers expect this O(1) version.
A hash set returns the first node seen twice, but uses O(n) space. Floyd's algorithm can find the entry too.
First, run slow and fast until they meet inside the cycle. Then move one pointer back to the head. Move both one step at a time, and they meet exactly at the cycle entry.
The head and the meeting point are the same distance from the entry. Meet, reset one pointer, then walk together.
Run the animation above on your own input, or watch the 1:14 video explanation of Linked List Cycle II with a dry run and Java code.