Detecting a Cycle in a Linked List Without Extra Memory
Developer interview question on data structures and memory complexity
The riddle
A linked list is a sequence of nodes, each of which points to the next one. Sometimes a node points back to a node already encountered: the list then forms a loop and never ends. How can you detect whether a loop exists without using extra memory proportional to the size of the list?
Need a hint?
Imagine two runners going through the list at different speeds: what happens if they run forever around a loop?
Show the answer and the solution
Answer: Floyd's algorithm: one pointer advances one node at a time, the other advances two; if they meet, there is a loop (O(n) time, O(1) memory).
The reasoning
Two pointers start at the beginning of the list: the tortoise moves one node per step, the hare moves two nodes per step. If the list ends, the hare reaches the end and we conclude there is no loop. If a loop exists, both pointers eventually enter it: the hare then catches up with the tortoise, since it gains one node at each step, and they meet on the same node. The number of steps is proportional to the size of the list, so the complexity is O(n) in time. Since only two pointers are stored, the extra memory is O(1).
What next?
Reasoning improves like memory: by practising often. Next, test yourself on our general knowledge quizzes.