Floyd’s Cycle Detection Algorithm

Floyd’s Cycle Detection Algorithm
Floyd’s Cycle Detection Algorithm

Floyd’s cycle-finding algorithm is a pointer algorithm that uses only two pointers, moving through the sequence at different speeds. It states the usage of Linked List in this algorithm 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

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.

For me, 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 on this example:

Imagine both the hare and the tortoise walk only on 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:

As you can check, their distance is shortened by 1 on each step of the algorithm.

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.

I will be discussing using Floyd’s Cycle Detection Algorithm, well known as ‘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 a miles ahead leap from Mercedes and will reach the racing line first followed by Mercedes sometime later.

B.Loop IS present

In this case again Bugatti will take a miles leap from Mercedes BUT as we have a loop in race track, he will be covering same track again and again , till he meets 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 Bugatti as ‘Car B’ and Mercedes as ‘Car M’

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

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

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

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

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

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

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

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

Here in 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 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 code:

public class FindLoop {

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);

}
}

Detecting start of a loop in singly Linked List:

As we have learnt 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.

What 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 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 start of the list and moving both pointer 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! 

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 the reach the meeting point. So by using simple speed, time and distance relation.

2(x+y)= x+2y+z
=> x+2y+z = 2x+2y
=> x=z
So by moving slowPointer to start of linked list, and making both slowPointer and fastPointer to move one node at a time, they both will reach at the point where the loop starts in the linked list.
As you will notice the below code is mostly the same as of 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.

package javabypatel;

public class ReturnStartNodeOfLoopInLinkList {

Node startNode;

public static void main(String[] args) {

ReturnStartNodeOfLoopInLinkList g = new ReturnStartNodeOfLoopInLinkList();

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.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n7);
n7.setNext(n8);
n8.setNext(n6);

Node loopNode = g.getStartNodeOfLoopInLinklist(g.startNode);

if(loopNode==null){
System.out.println(“Loop not present”);
}else{
System.out.println(“Start node of Loop is :”+loopNode.getData());
}
}

private 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.getNext()!=null){
tortoisePointer = tortoisePointer.getNext(); // ptr1 moving one node at at time
harePointer = harePointer.getNext().getNext(); // 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.getNext(); 
 harePointer = harePointer.getNext();
}

//returning start node of loop.
return tortoisePointer;

}
}

// this condition will arise when there is no loop in list.
return null;
}

}

Remove loop in Linked List:

Removing the loop in 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. 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 2: When the meeting node of both pointers in a loop is 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 1: 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 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.

package javabypatel;

public class RemoveLoopInLinkList {

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.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n7);
n7.setNext(n8);
n8.setNext(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.getNext()!=null){
slowPointer = slowPointer.getNext();
previousPointer = fastPointer.getNext(); // For capturing just previous node of loop node for setting it to null for breaking loop.
fastPointer = fastPointer.getNext().getNext();

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.setNext(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.getNext()!=fastPointer.getNext()){
  slowPointer = slowPointer.getNext();
  fastPointer = fastPointer.getNext();
 }
 fastPointer.setNext(null);
}

}
}
return startNode;
}

//Print linked list.
private void printList(Node startNode){
while(startNode!=null){
System.out.print(startNode.getData() + ” ” );
startNode=startNode.getNext();
}
}

}

To explore our courses, click here.

By Yogesh Kumar