Why it works
- Let a be the steps from the head to the loop's start and L the loop's length. When they meet, fast has walked twice as far as slow, and the extra distance is whole laps: slow has walked a multiple of L.
- So from the meeting point, a more steps bring slow to a + (a multiple of L), which is the loop's start. A pointer from the head reaches the start in the same a steps.
- Both move one step at a time in the second loop, so they first share a node exactly at the start, never earlier: before it one is still on the tail and the other on the loop.
Complexity
Time O(n): the first loop takes fewer than n rounds, as in Linked List Cycle, and the second exactly a, the length of the tail. Memory O(1): two pointers, no set of visited nodes.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗