Floyd’s Cycle Detection Algorithm

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

Report

What do you think?

Leave a Reply

Your email address will not be published. Required fields are marked *

GIPHY App Key not set. Please check settings