Home Tutorials Floyd’s Cycle Detection Algorithm

Floyd’s Cycle Detection Algorithm


Hello guys in this blog we are going to learn about the algorithm mentioned above, by its name it may tempt to sound a little bit scary but if you will read this article with full concentration then it will be a cake walk for you to code it in any programming/scripting language of your choice

So first let us understand what it is being used for, it is mainly used to detect loops or you may say a cycle in a linked list. The image below will clarify what a cycle in a linked list means,

Here like normally linked lists where the last node next pointer always points to null doesn’t exist there is a cycle being formed

So the algorithm for this problem is:

  1. Initialize 2 pointers and point them to the head of the list
  2. Move one pointer by 1 node and another by 2 nodes
  3. Check whether they meet somewhere in the linked list or not if they do then hurray we have detected a cycle but if it doesn’t then it’s a normal linked list 

Let’s understand this with an example we’ve a linked list(which has a cycle) as per the 1st step we will initialize 2 pointers (ptr1 and ptr2) and point them to the head of the list

There are total 8 nodes present in the above linked list ptr1 will move by 1 node as its distance and ptr2 by 2 nodes so now we will move the pointers

After this step ptr2 will complete one loop by moving from node 7 to node 3:

So here we got the node we were looking for and that’s node 7

This cycle detection problem is also known as Tortoise-rabbit problem where the tortoise moves by 1 node and rabbit by 2 nodes

Now coming to the coding part if you have been given a linked list (i.e. the head node of the linked list) and you want to detect the cycle using this algorithm I have coded it you can have a look at the code of the function (I have coded it in python)

def has_cycle(head):
    backward = head
    forward = head
    while(forward and forward.next):
        backward = backward.next
        forward = forward.next.next
        if(forward == backward):
            #cycle detected
            return 1
    #no cycle found
    return 0
Notify of

Inline Feedbacks
Read Comments

Ad Blocker Detected!