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

## 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****fastPointer** - Move
**slowPointer****fastPointer** - If at any point in the above traversal,

and**slowPointer**

are found to be pointing to the same node, which implies the list has a cycle**fastPointer**

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

at the intersected position.**fastPointer** - Move both the

and**fastPointer**

pointers by one node.**slowPointer** - 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

and **slowPointer**

that move 1 node and 2 nodes respectively before they meet each other at the pink node. From there the **fastPointer****slowPointer**** **node is reset** **to point to the head and both of

and **fastPointer**

are then moved by one node. The next point they meet will be the start of the cycle i.e the green node.**slowPointer**

Let,= Distance between the start of the Linked List and the start of the cycle.

xy= Distance between the start of the cycle to the point whereslowPointerandfastPointerfirst meet each other.l= Total distance of the cycle.Distance travelled byslowPointeron meetingfastPointeris

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

has covered a distance of **slowPointer**

, where **x + s*l + y**

is a non-negative integer.**s**

has covered a distance of **fastPointer**

, where **x + f*l + y**

is a non-negative integer.**f**

Since

travels twice the speed of **fastPointer**

, 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.**slowPointer**

So,x + f*l + y = 2(x + s*l + y)Solving this, we getx + y = f*l - 2s*lWe can say,f*l - 2s*l = (some integer) * l = k*lSo,x + y = kl, wherekis an integer

=>x = kl - y

Now, if we move

the start of the linked list will cover **slowPointer**

distance to meet **x**

, when **fastPointer**

will cover **fastPointer**

distance (because **kl-y****fastPointer**** **already has covered** **

distance).**y**

Since, **kl — y = x**** , **both** ****fastPointer**** **and **slowPointer**** **will cover** **

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 **x**

can complete some **fastPointer****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:

Please feel free to share with your fellow developers.