Detect a cycle in a linked list with O(1) extra space?
Options
- Store each visited node in a hash set and look for repeats
- Floyd's: a slow and a fast pointer meet when there is a cycle (Correct option)
- Reverse the list in place and compare it with the original
- Sort the nodes by value and look for any repeated nodes
Answer
Floyd's tortoise and hare: slow moves 1, fast moves 2; they meet if there is a cycle
Why
Use two pointers: the slow one moves 1 node per step, the fast one 2 nodes.
If the list ends, there is no cycle. If there IS a cycle, the fast pointer eventually laps the slow one inside the loop and they meet, like two runners on a circular track.
A set of visited nodes also works but uses O(n) memory.
Remember
Cycle detection: fast and slow pointers.