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!

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.