Fast & Slow Pointers
LC #141Easy
Linked List Cycle
Fast & Slow Pointers
AmazonGoogleMicrosoftAppleProblem
Detect if a linked list has a cycle, using O(1) memory.
linked-listfast-slow-pointers
Constraints
- ›0 ≤ n ≤ 10⁴
- ›-10⁵ ≤ Node.val ≤ 10⁵
- ›pos = -1 means no cycle; otherwise pos is the index of the node the tail connects to
- ›Must use O(1) memory
Example
Input
head = [3, 2, 0, -4], pos = 1Output
trueWhy
Tail node (-4) points back to node at index 1 (value 2), forming a cycle