Floyd’s Cycle Finding Algorithm Aka Hare and Tortoise algorithm

This algorithm is used to detect cycle in linked list.

Floyd’s cycle finding algorithm is a pointer algorithm which uses two pointers to find cycle in the given linked list.

Lets see how this algorithm uses these two pointers ---->

One pointer moves two step at a time while the other one moves one step at a time, this is somewhat like the story we have heard in our childhood in which hare 🐇 move faster than the tortoise 🐢 that is why it is also known as Hare and Tortoise algorithm.

If at some point of time, these two pointers meet each other then the given linked list has a cycle or if they don’t meet each other then the given linked list has no cycle.

Now we got the basic idea of how it works, we illustrate this using code->

In the problem you have been asked whether there is a cycle in the given linked list or not, so you have to return bool that is true or false and you’re are given the head of the node.

So first we make a bool function and check if head exists, and if head->next exists. If neither exists, then there is no cycle and we will return fasle.

Next we’ll initialize our pointers as slow and fast and they will start at the head node but as we already know slow one (tortoise) will move one step at a time and fast one (hare) will move two step at a time.

Now, Because fast pointer is moving faster so it will reach the end before the slow pointer. So as long as the fast pointer pointing at the node that isn’t null, and the next node isn’t null, we will continue checking things. Therefore, we will use a while loop to continue checking till condition become false.

Inside the while loop, we will check if the slow and fast pointer pointing to the same node. If yes, means there is cycleF then we can return true. Otherwise we will move the slow pointer by one node and fast by two nodes at a time.

Finally, if the condition on while loop become false, means that there is no cycle found in the given linked list and we can return false.

The time complexity of this algorithm is linear: O(n).

Thankyou for reading!

Happy Learning! ☺