Floyd’s cycle-finding algorithm is a pointer algorithm which uses two pointers. One pointers “walks” one step at a time and the second one walks two steps at a time. Floyd's cycle-finding algorithmFloyd’s cycle-finding algorithm

If you look at the image where the hare moves two steps and the turtle moves one step at the time, you will see that they will overlap on the f node at some point and you can conclude that the path contains a cycle. Now, that doesn’t mean that the f node is the start of the cycle. If you look at the image, the start of the cycle is the e node.

To find the start of the cycle, you move turtle to the start of the list (and leave hare at the meeting point - f node) and move them both one step at the time. The new meeting point (e in this case) is the start of the cycle.

We need a mathematical proof that this works.

Let:

  • l be the length of the loop (5 in the picture)
  • m be the distance from the start of the list to the start of the loop (4 in the picture)
  • k be the distance from the start of the loop to the ‘hare-turtle’ starting point (1 in this picture)

Distance traveled by hare is as twice as large than the distance traveled by the turtle.

$dist(turtle) = m + p * l + k$

$dist(hare) = m + q * l + k$

$q$ and $p$ tells how many times hare and turtle circled a loop and $q$ must be bigger than $p$ because the hare is as twice as fast.

As you can see, $m + k$ is the integer multiple of the length of the loop.