How do you detect whether a linked list contains a cycle, and why does the two pointer method work?
You use two pointers that start at the same place and move at different speeds. The fast one moves two nodes at a time and the slow one moves one. If the list has a cycle then they will meet. If it does not then the fast one reaches the end and you stop.
the list 1 -> 2 -> 3 -> None
slow walks one node at a time
fast walks two nodes at a time
And why does that work? Here is the argument. Suppose there is a cycle and the distance from the head of the list to the start of the cycle is a, and the length of the cycle is c. Then the slow pointer reaches the start of the cycle after a steps, and the fast pointer reaches it after a divided by two steps, which is sooner.
After that, both pointers are on the cycle, and the fast one goes around it one whole time for every half turn that the slow one does. So the fast one gains one full lap on the slow one every so many steps, and eventually the gap between them becomes exactly the length of the cycle, which means they land on the same node.
And if the list has no cycle then the fast pointer reaches the end of the list and gives back nothing, and the function says there is no cycle.
And the complexity is O of n for the time, where n is the number of distinct nodes, and O of 1 for the space. The fast pointer can travel up to twice around the list before the two of them meet, so the number of steps is bounded by twice n.
And there is a second way that is worth knowing about. You keep a set of the nodes you have seen. If you meet a node that is already in the set then you have been round the cycle and you have found it. That version is O of n for the space, because of the set, and it is often the version to write first because it is obvious.
So the rule to remember is this. The fast pointer goes twice as fast, and if they meet then there is a cycle.
The last question in this topic shows the code.