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++

Download   Run Code

Output:

Cycle Found

Java

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++

Download   Run Code

Output:

Cycle Found

Java

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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Mohit
Guest

nice algorithm..

Harald Sedlacek
Guest

How can i change the avatar?

Aditya
Guest