Algorithms and Data Structures · Middle · Question 24 of 75
How do you detect a cycle in a linked list with O(1) extra memory?
- ✓Correct answer: A slow and a fast pointer: they meet only if there's a cycle
- 2Count the nodes and compare with the list's length property
- 3Store every visited node in a
Setand check for repeats
Explanation
This is Floyd's "tortoise and hare" algorithm. If there's a cycle, the fast pointer eventually laps the slow one; if not, it reaches null. A Set also works but takes O(n) memory.