# Why does Floyd’s Cycle detection algorithm work?

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.

# 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 :

1. Declare 2 nodes say `slowPointer` and `fastPointer` pointing to the linked list head.
2. Move `slowPointer` by one node and `fastPointer` by 2 nodes till either of one reaches nil.
3. 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

1. Reset the `slowPointer` to point to the head of the linked list and keep the `fastPointer` at the intersected position.
2. Move both the `fastPointer` and `slowPointer` pointers by one node.
3. 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.

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.

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

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: