visual walkthrough
Linked List Cycle
Floyd's cycle detection in its simplest form.
The idea
Without a cycle, walking the list eventually hits null. With one, the walk goes round forever, so you need a way to notice.
Send two pointers, one twice as fast. If there's a loop, the fast one laps the slow one and they meet; if not, the fast one hits the end.
Complexity
| approach | time | space |
|---|---|---|
| Remember every node | O(n) | O(n) |
| Slow and fast pointers | O(n) | O(1) |