Linked List Cycle
Given the head of a singly linked list, determine whether following next pointers ever revisits a node (i.e. the list contains a cycle). Use constant extra memory.
- 0 ≤ number of nodes ≤ 10^4
- O(1) space required
- Linked list, so no random access
- Constant memory forbids a visited set
- A faster walker laps a slower one inside a loop
Two pointers moving at different speeds along a sequence of next links meet if and only if the sequence loops (Floyd). The same trick locates the middle in one pass and finds the cycle entry, all in O(1) space. Any function f: [1..n] -> [1..n] iterated from a start is an implicit linked list.
Advance a slow pointer one node per step and a fast pointer two nodes per step. If the fast pointer reaches null there is no cycle. If there is a cycle, once both pointers are inside it the gap between them shrinks by one each step, so they must meet within one lap. Return true when they point to the same node.
- A hash set of visited nodes is simpler but uses O(n) space; Brent's algorithm is a variant of the same race with fewer pointer moves.