visual walkthrough
Linked List Cycle II
The maths behind finding a cycle's start with Floyd's algorithm.
The idea
Slow and fast pointers prove there's a cycle when they meet, but they meet somewhere inside the loop, not necessarily at its start.
The maths works out so that the distance from the head to the cycle's start equals the distance from the meeting point to the start (going round). So restart one pointer at the head and step both one at a time.
Complexity
| approach | time | space |
|---|---|---|
| First node seen twice | O(n) | O(n) |
| Floyd's two phases | O(n) | O(1) |