Floyd's tortoise and hare algorithm

Problem

Given a linked list, determine wether or not it has a cycle in it.

Algorithm

The algorithm keeps track of two pointers named tortoise and hare. At each time step, move the tortoise one step forward and the hare two steps forward, and compare the two pointers. If the two pointers point to the same node, then there exists a cycle.

Below is a python implementation of the algorithm:

def floyd(head: Node) -> bool:
    tortoise = hare = head
    while hare and hare.next:
        tortoise = tortoise.next
        hare = hare.next.next
 
        if tortoise == hare:
            return True
    
    return False

This only requires one single pass through the list, hence its time complexity is $\mathcal{O}(n)$. Also, the algorithm does not keep an intermediate data structure, and its space complexity is $\mathcal{O}(1)$.

Correctness

If the list does not contain a cycle, then it is clear that the algorithm will return False. Thus, it suffices to consider only the case the list contains a cycle.

Let $\mu$ be the length of the preliminary part (before the cycle), and $\lambda$ be the length of the cycle. Now, we can label the nodes: the preliminary nodes will be labelled $-\mu ,\mu +1,\cdots ,-1$ (starting at the head), and the cycle nodes $0,1,\cdots ,\lambda -1$.

At time $\mu$, the tortoise will be at node $0$, and the hare will be at node $\mu \equiv r(\mathrm{mod}\lambda )$. (It has moved $2\mu$ nodes; the first $\mu$ nodes is the preliminary part.)

If $r=0$, tortoise and hare is at the same position, which proves our algorithm. Otherwise if $0<r<\lambda$, consider the pointers at time $\mu +\lambda -r$. The tortoise will be at node $\lambda -r\equiv -r(\mathrm{mod}\lambda )$, and the hare will be at node $r+2(\lambda -r)\equiv 2\lambda -r\equiv -r(\mathrm{mod}\lambda )$. Hence both pointers are at the same node, which completes our proof.

References

• Wikipedia contributors. (2023, November 8). Cycle detection. Wikipedia. https://en.wikipedia.org/wiki/Cycle_detection
• paw88789 (https://math.stackexchange.com/users/147810/paw88789), Proof of Floyd Cycle Chasing (Tortoise and Hare), URL (version: 2014-08-30): https://math.stackexchange.com/q/913529