Algorithm: Detecting cycles in a linked list

Detecting cycle in a linked list I

Problem Detect if there is a cycle in a singly-linked list. Do it in $O(n)$ time and $O(1)$ space.

Solution Assume without loss of generality that a list node never points to itself. To detect a cycle, we iterate the list with two pointers such that one pointer moves faster than the other. We argue that the two pointers eventually coincide (i.e. point to the same node) if the list contains a cycle.
Suppose that in each iteration, the faster pointer advances $m$ steps and the slower pointer advances one step. We check whether the two pointers coincide at the end of an iteration. Let $d(x,y)\in[0,\infty]$ denote the minimal number of moves a pointer has to made starting from node $x$ to reach node $y$. Let $A$ be the first node of the cycle visited by the slower pointer, and $B$ be the node the pointers point to when they coincide. Denote the number of nodes in the cycle by $k$.
When the two pointers coincide, the number of moves made by the faster pointer is $m$ times larger than the moves made by the slower pointer. Hence, the two pointers eventually coincide iff there exist integers $p,q,v,h\ge0$ such that $h=d(head,A) \ge 0$, $v=d(A,B)\le k-1$, and $h+pk+v=m(h+qk+v)$ with $m,k\ge 2$, which holds iff there exist $p,q,v\ge 0$ satisfying \begin{equation}k(m-1) > v(m-1) = k(p-mq)-h(m-1) \ge 0,\label{coin-eg1}\end{equation}which, by setting $X=p-mq$, can be be written as $$k (m-1) > kX - h (m-1) \ge 0.$$ If $k\ge h$, then all $p,q\ge 0$ such that $X=m-1$, namely $p=mq+m-1$, satisfy \eqref{coin-eg1}. If $k < h$, then there exists $n\ge 1$ such that $kn\ge h > k (n-1)$. In this case, observe that when $X=n(m-1)$, namely $p=mq+nm-n$, we have

　$kX-h(m-1) = kn(m-1) - h(m-1) \ge 0$, and
　$k(m-1) = kn(m-1) - k(n-1)(m-1) > kn(m-1) - h(m-1) = kX - h(m-1)$

It follows that all $p,q\ge 0$ such that $p=mq+mn-n$ satisfy \eqref{coin-eg1}. This concludes the proof.
Discussion. The above analysis gives two sufficient conditions for coincidence where the only constraint for $q$ is $q\ge 0$. By setting $q=0$, we see that one can detect the cycle at the $h+v<n$th iteration, which is already the minimal number possible. Also, $v=kp/(m-1)$, where $p$ is the minimal integer to make $v$ an integer. We can obtain the size of the cycle with an additional $k$ iterations after we found node $B$.

Detecting cycle in a linked list II

Problem Detect if there is a cycle in a singly-linked list, and if there is one, find the node where the cycle begins. Do it in $O(n)$ time and $O(1)$ space.

Solution We assume that the list contains a cycle and use the notations defined before. Iterate the list as we did in the previous solution and set $m=2$. By the above argument, there exist $p,q\ge0$ such that $h+pk+v=2(h+qk+v)$, which implies $h+v=k(p-2q)$. Hence, if a pointer advances $h$ steps from node $B$, it will reach node $A$ after looping the cycle $p-2q$ times. To find node $A$, we can launch two fresh pointers from the head and node $B$ respectively, both moving one node forward at a time. These two pointers will both point to node $A$ after $h$ moves. See here for an implementation of the algorithm.

Discussion. In this solution, we stipulate the ratio of speeds $m=2$ for the two pointers. I don't know if it is possible to find the node within the required complexity given an arbitrary ratio of speeds. Also, for the ease of proof, we check coincidence of the pointers only at the end of each iteration. A conscientious reader may want to prove the correctness of an algorithm that checks coincidence after each step, and see if it is indeed more efficient than the simplified version presented here.

Further readings

1. http://en.wikipedia.org/wiki/Cycle_detection