Detecting a cycle in a linked list
A singly linked list either ends in a null pointer or eventually loops back into itself. Using extra memory and time linear in the number of nodes, decide whether it has a cycle, and if it does, find the first node on the cycle and the cycle length.
History and references
Solved by Robert W. Floyd (attributed by Donald Knuth).
The standard answer is the tortoise and hare algorithm, which Donald Knuth attributed to Robert W. Floyd in 1969, although Floyd did not publish it. Advance one pointer by one node per step and another by two nodes per step. If there is a cycle they must meet inside it, and at that moment the number of steps taken by the slow pointer is a multiple of the cycle length . If the cycle starts after nodes, restarting one pointer at the head and moving both one node at a time makes them meet exactly at the first node of the cycle after steps, and one more lap measures . The whole procedure takes steps and constant memory, and Richard Brent gave a variant in 1980 that is often faster.
References
Solutions 0
Sign in or create an account to publish a solution