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
306+ registered