Why does Floyd’s Cycle detection algorithm work?

4 min readMay 8, 2021

Floyd’s Cycle detection algorithm or Hair Tortoise algorithm is used to detect if there is a cycle in a linked list. This algorithm is quite confusing if not analyzed mathematically.

If you are aware of the algorithm and want to check only the WHY, jump to the proof section.

What is a Linked List Cycle?

A linked list is said to have a cycle if the end of the linked list points to another node of the list.

Code

What is Floyd’s Cycle detection algorithm?

Floyd’s Cycle detection algorithm is used to detect whether the linked list has a cycle in it and what is the starting point(green node in the above diagram) of the cycle.

Algorithm to find whether there is a cycle or not :

Declare 2 nodes say slowPointer and fastPointer pointing to the linked list head.
Move slowPointer by one node and fastPointer by 2 nodes till either of one reaches nil.
If at any point in the above traversal, slowPointer and fastPointer are found to be pointing to the same node, which implies the list has a cycle

Algorithm to find the starting node of the cycle:

After figuring out whether there is a cycle or not perform the following steps

Reset the slowPointer to point to the head of the linked list and keep the fastPointer at the intersected position.
Move both the fastPointer and slowPointer pointers by one node.
The point at which they will intersect is the starting of the cycle.

Why does Floyd’s Cycle Algorithm works?

But can we prove whether the algorithm will even work?

Let us assume that the Linked list has a cycle that starts at the green node. As per the algorithm, we have 2 traversal pointers slowPointer and fastPointer that move 1 node and 2 nodes respectively before they meet each other at the pink node. From there the slowPointer node is reset to point to the head and both of fastPointer and slowPointer are then moved by one node. The next point they meet will be the start of the cycle i.e the green node.

Let,
x = Distance between the start of the Linked List and the start of the cycle.y = Distance between the start of the cycle to the point where slowPointer and fastPointer first meet each other.l = Total distance of the cycle.Distance travelled by slowPointer on meeting fastPointer is

When they first meet each other i.e at the pink node,

slowPointer has covered a distance of x + s*l + y , where s is a non-negative integer.

fastPointer has covered a distance of x + f*l + y , where f is a non-negative integer.

Since fastPointer travels twice the speed of slowPointer , it would travel twice the distance in the same time as that of slowPointer. This we have calculated from simple time, speed, and distance relation.

So,
x + f*l + y = 2(x + s*l + y)Solving this, we get
x + y = f*l - 2s*l
We can say, f*l - 2s*l = (some integer) * l = k*lSo, x + y = kl, where k is an integer
=> x = kl - y

Now, if we move slowPointer the start of the linked list will cover xdistance to meet fastPointer, when fastPointer will cover kl-ydistance (because fastPointer already has covered ydistance).

Since, kl — y = x , both fastPointer and slowPointer will cover x i.e same distance after the pink node at some point to meet at the start point of the cycle. When we say at some point, i.e fastPointer can complete some kl distance out of which it has already covered y distance.

The concepts of Floyd’s Cycle detection algorithm can also be applied to many other linked list problems. So it is pretty necessary to understand the working of these.

I would love to hear from you

You can reach me for any query, feedback, or just want to have a discussion by the following channels:

Twitter — @gabhisek_dev

LinkedIn

Please feel free to share with your fellow developers.