# 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

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

Output:

Cycle Found

## Java

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

Output:

Cycle Found

## Java

Output:

Cycle Found

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

(4 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

nice algorithm..

Guest
Harald Sedlacek

How can i change the avatar?

Guest
Guest
Shivam Rajesh Ramdhani

int n = sizeof(keys) / sizeof(keys[0]);