Floyd’s algorithm for cycle detection is the fastest method to detect loop in linked list. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.
Let’s have a tortoise and a hare (name of the pointers) pointing to the beginning of the list with a cycle.
Let’s hypothesize that if we move tortoise 1 step at a time, and hare 2 steps at a time, they will eventually meet at a point.
The figure illustrates a list with a cycle. The cycle has a length of n and we are initially m steps away from the cycle. Also let’s say that the meeting point is k steps away from the cycle beginning and tortoise and hare meets after a total of i steps. Then following 2 conditions must hold:
- i = m + p * n + k
- 2i = m + q * n + k
The first one says that tortoise moves i steps and in these i steps it first gets to the cycle. Then it goes through the cycle p times for some positive number p. Finally it goes over k more nodes until it meets hare. A similar is true for hare. It moves 2i steps and in these 2i steps it first gets to the cycle. Then it goes through the cycle q times for some positive number q. Finally it goes over k more nodes until it meets tortoise. For some value of m, n, p, q, k and i, following equation will hold
2 ( m + p * n + k ) = m + q * n + k
Once tortoise and hare meet, let’s put tortoise back to the beginning of the list and keep hare where they met (which is k steps away from the cycle beginning).
Then, if we let them move m + k steps, tortoise would have to arrive at the point they met originally. Since m + k (from above m + k = (q – 2p) n) steps is a multiple of cycle length n, hare, in the mean time, would go through the cycle (q-2p) times and would come back to the same point (k steps away from the cycle beginning).
Now, instead of letting them move m + k steps, if we let them move only m steps, tortoise would arrive at the cycle beginning. Hare would go be k steps short of completing (q-2p) rotations. Since it started k steps in front of the cycle beginning, hare would have to arrive at the cycle beginning.
As a result, this explains that they would have to meet at the cycle beginning after some number of steps for the very first time (very first time because tortoise just arrived at the cycle after m steps and it could never see hare which was already in the cycle).
Now we know that the number of steps we need to move them until they meet turns out to be the distance from the beginning of the list to the cycle beginning, m. Of course, the algorithm does not need to know what m is. It will just move both tortoise and hare one step at a time until they meet. The meeting point has to be the cycle start and the number of steps must be the distance (m) to the cycle beginning. Assuming we know the length of the list, we can also, compute the length of the cycle of subtracting m from the list length.