###### Finding a Cycle in a Linked List | Floyd’s Tortoise and Hare Algorithm
Manas Sinha
Developer | Designer
Manas Sinha
Developer | Designer

## Floyd's Tortoise and Hare Algorithm

Finding a Cycle in a Linked List
The Floyd’s tortoise and hare algorithm has many applications in linked list:
• Detect whether there is a cycle in the list
• Find the starting point of the cycle (i.e. list 1->4->3->2->5->4, starting point is 4)
• Decide the length of the cycle
Here we will see the cycle detection. Linked list cycle can be found using a hash set but tortoise and hare algorithm is better in terms of space complexity.

## algorithm

To start this algorithm we have a linked list and its head pointer is given to us. It’s our job to find if there is a cycle present in the list or not.
The way this algorithm is implemented is that we have two pointers tortoise and hare and just as the name, hare moves 2x faster than the tortoise.
First we check that the Linked List is not empty
``````bool findLoop(Node* head){
return false;
}``````
Initialize tortoise with `head` and hare with `head`
``````bool findLoop(Node* head){
return false;
}``````
Now run the loop while the `hare` and `hare->next` is not NULL
``````bool findLoop(Node* head){
return false;
while(hare && here->next){
//..
}
}``````
Check if the hare and tortoise are pointing at the same node. If such is the case, return True
``````bool findLoop(Node* head){
return false;
while(hare && here->next){
if(tortoise == hare)
return true;
}
}``````
Otherwise, we will move the tortoise and hare. The tortoise moves one node at a time, and the hare moves two nodes at a time.
``````bool findLoop(Node* head){
return false;
while(hare && here->next){
if(tortoise == hare)
return true;
tortoise = tortoise->next;
hare = hare->next->next;
}
}``````
If the loop ends with hare and tortoise never pointing at the same node we return False
``````bool findLoop(Node* head){
return false;
while(hare && here->next){
if(tortoise == hare)
return true;
tortoise = tortoise->next;
hare = hare->next->next;
}
return false;
}``````
Floyd’s tortoise algorithm relies on the fact that if both pointers are moving at a different pace, the gap between them will keep on increasing to a limit, after which it’ll be reset to zero if a cycle exists.
Just like if you and your friend are driving in a circle with your friend moving twice at fast as you, You both will reach the starting point again together. It’s just that you will reach there after one revolution and your friend will be there after two revolutions.
Here’s an animation for you because I have a lot of free time:

### This Post Has 2 Comments

1. Beej

Neat algorithm!

Typo on line 6: here->next should be hare->next.

And the algorithm as-is always returns True for lists greater than length 1 because hare and tortoise both point to head to start (making it so the hare “caught” the tortoise immediately). Did you mean to: