Floyd's Cycle Detection

There is a famous algorithm called Floyd’s Cycle Detection Algorithm aka Tortoise and Hare Algorithm. It is used to detect a cycles in a list.

The tortoise is the slow pointer and the hare as fast pointer. The hare will travel in strides of 2 while the tortoise will travel in strides of 1.

Imagine the following scenario — a linked list with a cycle.

Some notation that we will use: $m$ is the distance from the start of the list to the start of the cycle, $P$ is the length of the cycle, and $k$ is the distance from the start of the cycle to the point where the hare and tortoise meet.

If one reached the end of the list, there is no cycle. If the two meet then there are 2 scenarios that can happen:

$$\begin{cases} i = m + k + aP & \exists\, a \in \mathbb{Z} \\ j = m + k + bP & \exists\, b \in \mathbb{Z} \end{cases}$$

where

$$\begin{aligned} a &:= \text{total loops the tortoise traveled} \\ b &:= \text{total loops the hare traveled} \\ i &:= \text{total distance tortoise traveled} \\ j &:= \text{total distance hare traveled} \end{aligned}$$

Since the hare is traveling at twice the speed of the tortoise, if the two ever meet, the hare has traveled twice the distance. Therefore:

$$j = 2i$$

With some simple algebra

$$\begin{aligned} m + k + bP &= 2\bigl((m+k) + aP\bigr) \\ m + k &= bP - 2aP \\ \Rightarrow\quad i &= bP - 2aP + aP \\ &= (b - a)P \end{aligned}$$

The next step is to put the hare at the beginning of the list, but this time have both the tortoise and the hare take strides of 1. The point at which the 2 meet will be the start of the cycle.

Since the tortoise is currently at $(b-a)P$ when the hare travels $m$ steps:

1. The hare is at $m$
2. The tortoise is at $(b - a)P + m$

We can rearrange the tortoise to have traveled $m + (b - a)P$ or taking $m$ steps then an integer multiple of $P$. Since there exists a cycle, traveling an integer multiple of $P$ around the cycle will land you at the beginning of the cycle.