New update is available. Click here to update.

Floyd’s Cycle Detection Algorithm

Yogesh Kumar
Last Updated: Aug 13, 2022
MEDIUM

Introduction

Floyd’s cycle detection algorithm is a pointer algorithm that uses only two pointers, moving through the sequence at different speeds. The article states the usage of this algorithm in Linked List and its output.

The purpose is to determine whether the linked list has a cycle or not. First, you keep two pointers of the head node. At each iteration, you move one of the pointers by two steps and the other one by one step. So you have two pointers tortoise and the hare. Eventually one of the two cases will happen:

  • Hare will reach the tail of the linked list(null), which means that there is no cycle in it.
  • Hare will meet tortoise, which means that there is a cycle
     

The most intuitive way of seeing this is as follows:

In each step of the algorithm, the tortoise walks 1 node, and the hare walks 2 nodes. In practice, the tortoise gets away by 1 distance unit, and then the hare gets nearby 2 distance units. In practice, it’s just like in each step, the tortoise stays stationary and the hare moves by 1 step.

Just, for instance, let’s check out this example:


example to depict Floyd’s Cycle Finding Algorithm

Imagine both the hare and the tortoise walk only in counter-clockwise order (1 -> 2 -> 3 -> 4…). The hare starts at node 4 and the tortoise at node 1. Their distance is 4->5->6->7->8->9->10->1, so, 7 steps of distance.

Now, let’s create a table of where the hare and the tortoise will be until they meet:

table to depict the solution

As you can check, their distance is shortened by 1 on each step of the algorithm if they are in a loop. They are bound to meet, if there exists a loop.
We can use this logic to find a loop in a singly linked list.

Find loop in Singly Linked List

Given a linked list we need to determine if a loop is present in the list or not. Basically when a loop is present in the list then two nodes will be pointing to the same node as their next node.

Recommended: Please try out this problem on CodeStudio, before moving on to the solution

We will be discussing Floyd's Cycle Detection Algorithm, well known as the ‘tortoise-hare’ algorithm. Well, as we are in the 21st century, and an era of supercars, I will be using some cars to explain the algorithm.

Suppose we have two cars namely Bugatti Veyron and Mercedes Benz, as we know top speed of Bugatti is double of Mercedes, and both are supposed to have a race and we have to determine whether the race track has a loop or not.

Clearly, there will be two cases

A. Loop is NOT present

In this case, Bugatti will take miles ahead leap from Mercedes and will reach the finishing line first followed by Mercedes sometime later.

B. Loop IS present

In this case, again Bugatti will take miles ahead leap from Mercedes BUT as we have a loop in the race track, it will be covering the same track again and again and will meet Mercedes rider again during the course, and he will be like “Dude! I think we met earlier. Aren’t we stuck in a LOOP or something?”

Well, this racing example can be understood more clearly, by the following picture representation, where the racecourse is marked by different flags. Here on we will be referring to Bugatti as ‘Car B’ and Mercedes as ‘Car M’

Initially, both the cars are at flag-1 together for the first time.


Find loop in Singly Linked List

When the next reading was taken, Car B has already taken a leap and reached flag-3 while Car M was at flag-2.


Find loop in Singly Linked List

In the next time interval Car B has reached flag-5 and Car M is at flag-3.


Find loop in Singly Linked List

Now Car B is at flag-7 and Car-M is at flag-4.


Find loop in Singly Linked List

Well Car B has completed the loop, still unaware, and reaches flag-3 whereas Car M is at flag-5.


Find loop in Singly Linked List

Moving ahead in loop Car B reaches flag-5 and Car-M has reached flag-6.

Find loop in Singly Linked List

At this instant, both are at the same flag. So they will come to notice that they are stuck in a loop.


Find loop in Singly Linked List

Turning geek mode on, we will be using the above example to solve our linked list problem.

Here in the place of cars, we will be having two pointers,

  • slowPointer 
  • fastPointer
     

which will traverse through the loop and where fast-Pointer move double the speed of slow-Pointer covering two nodes in one iteration as compared to one node of slow-Pointer.

We will be having the same case here:

  • In the absence of LOOP: In this case, the fast-Pointer will hit the end of the loop, when it will be assigned a null value.
  • If the presence of LOOP: In this case, the fast-Pointer will move through the loop once and meet the slow-Pointer, where both will be pointing to the same node. Set the loop Found flag to true and break out of the loop.
     

Below is the Java implementation of the algorithm:

public class FindLoop {
  
 
    /* Linked list Node*/
public static class ListNode {
        int data;
        ListNode next;
        ListNode(int d)
        {
            data = d;
            next = null;
        }
    }
public static void isLoopPresent(ListNode nodeHead){

ListNode slowPointer,fastPointer;
        slowPointer = nodeHead;
        fastPointer = nodeHead;

//we will be using a flag to know if loop was found
boolean loopFound = false;

while(fastPointer != null){

    fastPointer = fastPointer.next;

    if(fastPointer != null){
        fastPointer = fastPointer.next;
        slowPointer = slowPointer.next;
    }


    if(fastPointer == slowPointer){
        loopFound = true;
        // we need to break otherwise it will go on forever
        break; 
    }
}

if(loopFound){
    System.out.println("Loop is Present");
}else{
    System.out.println("No Loop Found");
}
}
public static void main(String [] args){

    /*
    Creating a Linked List of eight nodes
    having a loop at (node 3)

    HEAD-->1-->2-->3-->4-->5
                  ^       |
                  |       v
                  8<--7<--6

    */

    // creating 8 independent nodes
    ListNode nodeOne = new ListNode(1);
    ListNode nodeTwo = new ListNode(2);
    ListNode nodeThree = new ListNode(3);
    ListNode nodeFour = new ListNode(4);
    ListNode nodeFive = new ListNode(5);
    ListNode nodeSix = new ListNode(6);
    ListNode nodeSeven = new ListNode(7);
    ListNode nodeEight = new ListNode(8);

    //Head node pointing to first node of linked list
    ListNode nodeHead = nodeOne;

    // creating a dependency in nodes by linking node to one another
    nodeOne.next = nodeTwo;
    nodeTwo.next = nodeThree;
    nodeThree.next = nodeFour;
    nodeFour.next = nodeFive;
    nodeFive.next = nodeSix;
    nodeSix.next = nodeSeven;
    nodeSeven.next = nodeEight;
    nodeEight.next = nodeThree; // this line creates the loop

    //calling method to evaluate
    isLoopPresent(nodeHead);
}
}


Time complexity is O(N) where N is the number of nodes in the linked list, space complexity is O(1) as you use only two pointers.

Detecting start of a loop in Singly Linked List

As we have learned above, we can detect with the help of our beloved cars(i.e slowPointer and fastPointer) that if a loop is present in the given Linked List.

Recommended: Please try out this problem on CodeStudio, before moving on to the solution

What do we need to do in case we need the starting point of the loop?

  • Once we know for sure that a loop is present.
  • Move the slowPointer to the start of the list,(i.e headNode) and let fastPointer remain there at the meeting point.
  • Now move both the pointers one node at a time(Yes! You heard it right. Now even fastPointer moves at one node at a time).
  • The point where both pointers will meet is our required start of the loop.
     

By now it had already started itching in mind that, Why the hell does moving slowPointer to the start of the list and moving both pointers one step at a time will find the start of the loop? (insert some angry smiley).

For that, we have a small proof, which will explain everything in a jiffy. Trust me! 

Detecting start of a loop in singly Linked List

Distance travelled by slowPointer before meeting= x + y

Distance travelled by fastPointer before meeting = (x + y + z) + y

= x + 2y + z

Since fastPointer travels with double the speed of slowPointer, and time is constant for both when they reach the meeting point. So by using simple speed, time, and distance relations.

2(x+y)= x+2y+z

=> x+2y+z = 2x+2y

=> x=z

So by moving slowPointer to the start of the linked list, and making both slowPointer and fastPointer move one node at a time, they both will reach the point where the loop starts in the linked list.

As you will notice the below code is mostly the same as the above code where we needed to detect, whether a loop is present or not, and then if a loop is there we move forward to tracing its starting location.

public class ReturnStartNodeOfLoopInLinkList {


    public static class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }

    public static Node getStartNodeOfLoopInLinklist(Node startNode) {
        Node tortoisePointer = startNode; // Initially ptr1 is at starting location.
        Node harePointer = startNode; // Initially ptr2 is at starting location.
        // If ptr2 encounters NULL, it means there is no Loop in Linked list.
        while (harePointer != null && harePointer.next != null) {
            tortoisePointer = tortoisePointer.next; // ptr1 moving one node at at time
            harePointer = harePointer.next.next; // ptr2 moving two nodes at at time
            // if ptr1 and ptr2 meets, it means linked list 
contains loop.
            if (tortoisePointer == harePointer) {
                //After meet, moving tortoisePointer to start node of list.
                tortoisePointer = startNode;

                //Moving tortoisePointer and harePointer one node at a time till the time they meet at common point. 
                while (tortoisePointer != harePointer) {
                    tortoisePointer = tortoisePointer.next;
                    harePointer = harePointer.next;
                }

                //returning start node of loop.
                return tortoisePointer;
            }
        }
        // this condition will arise when there is no loop in list.
        return null;
    }

    public static void main(String[] args) {

        Node n1 = new Node(10);
        Node n2 = new Node(20);
        Node n3 = new Node(30);
        Node n4 = new Node(40);
        Node n5 = new Node(50);
        Node n6 = new Node(60);
        Node n7 = new Node(70);
        Node n8 = new Node(80);

        n1.next = (n2);
        n2.next = (n3);
        n3.next = (n4);
        n4.next = (n5);
        n5.next = (n6);
        n6.next = (n7);
        n7.next = (n8);
        n8.next = (n6);

        Node loopNode = getStartNodeOfLoopInLinklist(n1);
        if (loopNode == null) {
            System.out.println("Loop not present");
        } else {
            System.out.println("Start node of Loop is :" + loopNode.data);
        }
    }


}
Time complexity is O(N) where N is the number of nodes in the linked list, space complexity is O(1) as you use only two pointers.

Remove loop in Linked List

Removing the loop in the Linked list is simple, after identifying the loop node, we just require the previous node of the loop node, So that we can set it to NULL.

Recommended: Please try out this problem on CodeStudio, before moving on to the solution

For identifying the previous node of the loop node, we will keep the previousPointer pointing to just the previous node of the loop node

CASE 1: When the meeting node of both pointers in a loop is the start node or root node itself, in this case by just setting previousPointer to NULL will work because previousPointer is already pointing to the last node of the linked list.

CASE 2: When the meeting node of both pointers in a loop is in-between the linked list, in this case, the first task is to identify the start of the loop node in the way as we saw above and then by setting fastPointer, which is already pointing to last node of the list to NULL will work.

public class RemoveLoopInLinkList {
    public static class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }

    }

    Node startNode;
    public static void main(String[] args) {
        RemoveLoopInLinkList g = new RemoveLoopInLinkList();
        Node n1 = new Node(10);
        Node n2 = new Node(20);
        Node n3 = new Node(30);
        Node n4 = new Node(40);
        Node n5 = new Node(50);
        Node n6 = new Node(60);
        Node n7 = new Node(70);
        Node n8 = new Node(80);
        g.startNode = n1;
        n1.next = (n2);
        n2.next = (n3);
        n3.next = (n4);
        n4.next = (n5);
        n5.next = (n6);
        n6.next = (n7);
        n7.next = (n8);
        n8.next = (n6);
        //Detect and Remove Loop in a Linked List
        Node newStart = detectAndRemoveLoopInLinkedList(g.startNode);
        g.printList(newStart);
    }
    private static Node detectAndRemoveLoopInLinkedList(Node startNode) {
        Node slowPointer = startNode;
        Node fastPointer = startNode;
        Node previousPointer = null;
        while (fastPointer != null && fastPointer.next != null) {
            slowPointer = slowPointer.next;
            previousPointer = fastPointer.next; // For capturing just previous node of loop node for setting it to null for breaking loop.
            fastPointer = fastPointer.next.next;
            if (slowPointer == fastPointer) { // Loop identified.
                slowPointer = startNode;
                //If loop start node is starting at the root Node, then we slowpointer, fastpointer and head all point at same location. 
                //we already capture previous node, just setting it to null will work in this case.
                if (slowPointer == fastPointer) {
                    previousPointer.next = (null);

                } else {
                    // We need to first identify the start of loop node and then by setting just previous node of loop node next to null.  
                    while (slowPointer.next != fastPointer.next) {
                        slowPointer = slowPointer.next;
                        fastPointer = fastPointer.next;
                    }
                    fastPointer.next = (null);
                }
            }
        }
        return startNode;
    }
    //Print linked list.
    private void printList(Node startNode) {
        while (startNode != null) {
            System.out.print(startNode.data + " ");
            startNode = startNode.next;
        }
    }
}


Time complexity is O(N) where N is the number of nodes in the linked list, space complexity is O(1) as you use only two pointers.

Conclusion

In this article, we discussed Floyd’s cycle detection algorithm with its implementation in java. The article also discussed the different variations of problems based on Floyd’s cycle detection algorithm. 

If you want to master the linked list then you should read this article.

If you are preparing for interviews at top product-based companies then CodeStudio is your one-stop destination. It is a great platform developed by some aspiring enthusiasts and working professionals who have experience in companies like Google, Amazon, Microsoft. 

At CodeStudio you get interview problems, interview experiences, and practice problems that can help you to land your dream job.  

Happy learning 
#BeCurious

Was this article helpful ?
3 upvotes