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

By Manas | 22 March 2021 | 1 mins read

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){
    if(!head) 
        return false;
}
Initialize tortoise with head and hare with head
bool findLoop(Node* head){
    if(!head) 
        return false;
    Node* tortoise = head;
    Node* hare = head;
}
Now run the loop while the hare and hare->next is not NULL
bool findLoop(Node* head){
    if(!head) 
        return false;
    Node* tortoise = head;
    Node* hare = head;
    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){
    if(!head) 
        return false;
    Node* tortoise = head;
    Node* hare = head;
    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){
    if(!head) 
        return false;
    Node* tortoise = head;
    Node* hare = head;
    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){
    if(!head) 
        return false;
    Node* tortoise = head;
    Node* hare = head;
    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:

LEAVE A COMMENT

If you like the post leave a comment and share it.

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:

    tortoise = head
    hare = head->next

    to start?

Leave a Reply