Tortoise and Hare Algorithm

This is an algorithm to detect cycles in a Linked List. It uses 2 pointers, one slow moving and other fast. See for more details.

Starting from the node head, the slow pointer goes to head->next and the fast pointer goes to head->next->next. The algorithm terminates if any of the next field is null, as that means there’s no cycle present. It finds a cycle if both the slow and fast pointer point to the same node. We can also find out the starting point of the cycle with this

Why does it work?

• If there’s a cycle, all pointers starting from head and following next will eventually just be moving between nodes of the cycle.
• The distance between the fast and slow moving pointers increases by 1 after each step.

Combining the above points, both the fast and slow pointers will eventually be moving between nodes of the cycle. As their distance increases by 1 each time, eventually their distance will become a multiple of the length of the cycle. At that time, they will be pointing to the same node.

Consider the above cycle, the slow and fast pointers will move as shown in the following table. Slow and Fast column contains the node index. Distance means the number of links to follow to get from slow to fast.

Iteration	Slow	Fast	Distance
1	1	1	0
2	2	3	1
3	3	5	2
4	4	7	3
5	5	4	4
6	6	6	5

The algorithm terminates at iteration 6. Note that the distance between the pointers becomes a multiple of cycle length at which point they will be pointing the same node.

Finding the starting point of the cycle

After having determined there is a cycle, reset the slow pointer to point to head. Now move both slow and fast pointers 1 node at a time. They will meet at the starting point of the cycle.

Consider the above figure. $a$ is the distance travelled by the pointers to enter the cycle, $b$ is the distance travelled from the starting point of the cycle and $L$ is the length of the cycle.

$$\begin{array}{rl}{x}_{slow}& =a+mL+b,\text{ where }m\in \mathbb{N}\\ x_{fast}& =a+nL+b,\text{ where }n\in \mathbb{N}\end{array}$$

Since fast pointer moves at twice the speed of slow pointer, it will have covered twice the distance. Which means

$$\begin{array}{rl}{x}_{fast}& =2x_{slow}\\ ⟹a+mL+b& =2(a+nL+b)\\ ⟹b& =(m-2n)L-a\end{array}$$

Consider what happens after slow pointer is set to head. The slow pointer has to follow distance $a$ to reach the head of the cycle. Acoording to the last equation we can see that even the fast pointer will reach the head of the cycle after travelling distance $a$. This is because it is at distance $b$ from the start, and $b+a$ is a multiple of the length of the list.