Floyd's Cycle Detection Algorithm Proof In Laymen

Question

I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1).

I have looked through various proofs proving that:

• If there is a cycle, at some point the tortoise and the hare will meet. I understand that at some point, both will be within the cycle, but how do we know that they will eventually meet?
• The time complexity will equal O(N), where N = # of nodes.

I do not care about the case where we want to find the START of the cycle, only about proving that if there is a cycle, then the two pointers will meet at a point within the cycle, and that the time complexity is O(N).

None of these proofs make intuitive, logical sense to me.

Can someone PLEASE explain the two bullet points above in an intuitive manner?

If there is math in the proof, it would be great if you could explain all parts of the proof that would not make logical sense to someone without a CS degree. Thanks!

• gnasher729: Also look at Brent's algorithm which is faster on average. It does more steps, but less work per step.
• gnasher729: If tortoise and hare are in the cycle, and the hare is k steps behind, then with every iteration tortoise moves one step, hare moves two steps, so hare gets one step closer, and after k steps the meet.

Answer 1

The easiest way to understand this is really to draw it out and move your fingers on a graph, so I recommend literally pulling out a piece of paper to follow along.

Picture the part before the cycle as a line, and the cycle is a circle. So we have a straight line of arrows pointing into a circle of arrows. The length of the line is X steps, and the length of the circle is Y steps.

After X steps, the tortoise has gotten into the cycle, and the hare is further ahead, so it definitely is in the cycle too.

To understand why the tortoise and hare meet after they get into the cycle, think about the distance between the two in the circle. Assume the hare is BEHIND the tortoise--it's a circle, so while the hare is ahead, it's also fine to think of it as behind. It's at most Y steps behind in the circle, because the circle is only size Y.

At each step, the hare moves two steps, and the tortoise only moves one step, so the hare "catches up" one step. Eventually it will catch up to the tortoise. It catches up in the number of steps the hare started behind the tortoise, again at most Y steps.

So it does catch up, and it catches up in at most X + Y steps.

• gnasher729: "The easiest way to understand this is really to draw it out and move your fingers on a graph, so I recommend literally pulling out a piece of paper to follow along." +1 for that.

Answer 2

1. Detecting cycle using Floyd's cycle detection algorithm - for this we need answer to the question: what's the guarantee that the hare and the tortoise will meet?

2. Detecting the starting point of the cycle (in a linked-list) - As per the behavior of Floyd's algorithm, i.e., from the meeting point (μ) of the hare H and tortoise T, T starts moving 1 step at a time from μ and H starts moving 1 step at a time from the starting point b of the linked-list and they meet up at the starting point c of the cycle, it is evident that the distance between μ and c is equal to that between b and c. We will have to prove this.

---

To answer point 1, let's assume that there is a cycle. We know that H moves twice as fast as T. Let's say T is at some arbitrary point ahead of H, e.g., H is at point 1 and T is at point 5 on a number line as shown below:

enter image description here

Since, T takes 1 step at a time and H takes 2 steps at a time, the distance between T and H keeps decreasing by 1 in each step. That means they will converge after some definite number (4 in this case) steps.

Now, in Floyd's algorithm, once both of them enter the cycle, at some point in time H will either fall behind T or simply meet at some point without falling behind. Also, due to the cycle, it can be treated as an infinite sequence now and the above logic of convergence will hold, which means the hare and tortoise will meet at some point μ.

---

To answer point 2, let's refer to this diagram:

enter image description here

L is the length of the cycle. c is the beginning of the cycle. μ is the point where H and T meets.

We need to prove that: \begin{equation} L - ∂ = x \end{equation}

Let the distance travelled by T be: \begin{equation} D_T = x + nL + ∂ \end{equation}

where n is an integer representing some number of times the tortoise has completed the cycle before meeting at μ.

Let the distance travelled by H be: \begin{equation} D_H = x + mL + ∂ \end{equation} where m is an integer representing some number of times the hare has completed the cycle before meeting at μ.

We know that H moves twice as fast as T, hence \begin{equation} D_H = 2D_T \end{equation}

Therefore, \begin{equation} x + mL + ∂ = 2x + 2nL + 2∂ \Rightarrow x = L(2n - m) - ∂ \end{equation}

Since, the length of the cycle doesn't actually change, hence we can ignore the factor of \begin{equation} (2n-m) \end{equation}

Which means, we can say that: \begin{equation} x = L - ∂ \end{equation}

Therefore, when the hare pointer and the tortoise pointer meet at some point in the cycle, one of them can be put back to the beginning of the list and then both can be moved one step at a time and the point they meet will be the start of the cycle.

Answer 3

Assume there is a cycle of length r, which is entered after m steps. Once you enter the cycle, you stay in the cycle. After either m steps, or after 1 step if m = r, both tortoise and hare are in the cycle. Either they are in the same position, or the hare is k steps behind the tortoise for some 1 ≤ k ≤ r-1. With every step for the tortoise, the hare gets one step closer, and after k steps they meet for the first time.

(The case m = 0 had to be handled carefully because meeting after 0 steps doesn't count obviously).

Or easier: Let k be the smallest multiple of r which is ≥ m and ≥ 1. After k iterations, the tortoise is at position k which is in the cycle, and the hare is k positions further. Since k is a multiple of r, he is an integral number of cycles further, so he is in the first place.