Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Detecting start of a loop in Singly Linked List
3.
Remove loop in Linked List
4.
Frequently Asked Questions
4.1.
What is the Floyd algorithm for cycles?
4.2.
What is the complexity of Floyd's cycle-finding algorithm?
4.3.
What is the difference between Dijkstra and Floyd algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Floyd’s Cycle Detection Algorithm

Yogesh Kumar
12 upvotes

## 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:

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:

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 Coding Ninjas Studio, 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.

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 the 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 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 Coding Ninjas Studio, 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!

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.``````

Also see,  Rabin Karp Algorithm

## 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 Coding Ninjas Studio, 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.

## Frequently Asked Questions

### What is the Floyd algorithm for cycles?

The Floyd's Cycle Detection Algorithm, also known as the "Tortoise and the Hare" algorithm, detects cycles in a sequence by using two pointers moving at different speeds. If there's a cycle, the two pointers will eventually meet.

### What is the complexity of Floyd's cycle-finding algorithm?

The time complexity of Floyd's cycle-finding algorithm is O(μ + λ), where μ is the index of the first element in the cycle, and λ is the length of the cycle. The algorithm has linear time complexity for cycle detection in linked lists.

### What is the difference between Dijkstra and Floyd algorithm?

Dijkstra's algorithm finds the shortest path from one source to all vertices in a weighted graph, suitable for non-negative weights. Floyd-Warshall algorithm, a dynamic programming approach, finds shortest paths between all pairs of vertices, accommodating negative weights (excluding negative cycles).

## 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.

Also Read - Kadanes Algorithm

If you are preparing for interviews at top product-based companies then Coding Ninjas Studio 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 Coding Ninjas Studio you get interview problems, interview experiences, and practice problems that can help you to land your dream job.

Happy learning

Live masterclass