Detect Cycle in a linked list (Floyd’s Cycle Detection Algorithm)

In this post, we will see how to detect cycle in a a linked list using Hashing and Floyd’s Cycle Detection Algorithm.

 

For example, below linked list has a cycle in it

Floyd’s Cycle Detection Algorithm

 

1. Using Hashing:

 

Simple solution would be to use hashing. The idea is to traverse the given list and insert each encountered node into a set. Now, if the current node already present in the set (ie. it is seen before), that means a cycle is present in the list.

 
C++ implementation –
 

Download   Run Code

Output:

Cycle Found

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 


 

2. Floyd’s Cycle Detection Algorithm:

 

Floyd’s Cycle Detection Algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The idea is to move fast pointer twice as quickly as the slow pointer and the distance between them increases by 1 at each step. If at some point both meet, we have found a cycle in the list, else if we have reached the end of the list, no cycle is present. It is also called the “tortoise and the hare algorithm”.

 
C++ implementation –
 

Download   Run Code

Output:

Cycle Found

 

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Mohit
Guest
Mohit

nice algorithm..

wpDiscuz