Detect loop in Linked list.
Identify start node of loop in Linked list.
Remove loop in Linked list.
What is Loop in Linked list?
Generally, the last node of the linked list points to NULL, which is a indication of end of list.
But in Linked list containing Loop, last node instead of pointing NULL, it points to some of the internal node/starting node/itself.
In this case, If we traverse the Linked list node one by one, our traversal will never ends as it goes in loop.
Check below images for better understanding on how Linked list containing loop looks like.
Algorithm
Before going into detecting loop in linked list, Lets understand few basic points with help of example.
1. Jayesh and Khyati daily goes for jogging at Circular park(Park is completely circular of 1 Km).
2. Jayesh is bit lazy and jogs at "x" speed. Khyati is more energetic and jogs at 2x speed.
3. It means, when they both start from same point, and when Jayesh complete half jogging track,
Khyati will complete one jogging track round and reached at starting place again.
So if they both starts from common point, Jayesh running at speed "x" and Khyati running at speed "2x", Will they both meet again?
They will surely meet at the same location they started from.
Look at below image for better understanding.
Now, instead of starting from same point, if the starting point for Jayesh and Khyati is different still they will meet?
Yes they will meet. Not at same place but at some point in track.
Look at below image for better understanding.
They are meeting at some point because of the circular track and speed in which both are traveling.
Now, If Jayesh travels at "x" speed and Khyati travels at "3x" speed, still they both will meet, but numbers of complete cycles Khyati will perform and then meet Jayesh might increase.
Now, Lets look at our original problem
Detect loop in Linked list. (Floyd's Cycle detection algorithm)
So the algorithm behind identifying the loop in linked list is very similar to our jogging track example.
STEP 1:
Take 2 pointers ptr1 and ptr2, both pointing at the start node initially.
STEP 2:
STEP 2:
Move ptr1 forward one node at a time and move ptr2 forward two nodes at same time.
STEP 3:
STEP 3:
ptr2 is running at double speed, so definitely it will be ahead of ptr1,
- If ptr2 encounters NULL, it means there is no loop in a Linked list and stop execution.
- If linked list contains loop, then ptr2 at some point will enter in the loop. some time later ptr1 will also enter in the loop.
eventually they will meet at some point.
(From our jogging track example, we have already seen that)
If they both meet, it means Linked list contains loop and stop execution.
Detect loop in linked list (in Java)
package javabypatel;
public class DetectLoopInLinkedList{
private Node startNode;
public static void main(String[] args) {
DetectLoopInLinkedList detectLoopInLinkedList = new DetectLoopInLinkedList();
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);
detectLoopInLinkedList.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);
if(isLoopPresent(detectLoopInLinkedList.startNode)){
System.out.println("Loop is present in list");
}else{
System.out.println("No Loop present in list");
}
}
private static boolean isLoopPresent(Node startNode){
Node slowPointer = startNode; // Initially ptr1 is at starting location.
Node fastPointer = startNode; // Initially ptr2 is at starting location.
while(fastPointer!=null && fastPointer.getNext()!=null){ // If ptr2 encounters NULL, it means there is no Loop in Linked list.
slowPointer = slowPointer.getNext(); // ptr1 moving one node at at time
fastPointer = fastPointer.getNext().getNext(); // ptr2 moving two nodes at at time
if(slowPointer==fastPointer) // if ptr1 and ptr2 meets, it means linked list contains loop.
return true;
}
return false;
}
}
Node.java
package javabypatel;
public class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
Why increase pointer by two while finding loop in linked list, why not 3,4,5?
So, the condition here is you cannot change the speed of ptr1, it has to move one node at a time.but the choice for ptr2 to move can be 2 nodes at a time, 3 nodes at a time or any number of nodes at a time.
More the gap in which both pointers move forward, more the time they might take in worst case to meet.
So the lowest possible iteration in which we can find their meeting points is by moving ptr2 two nodes at a time.
Identify start node of loop in linked list.
If the linked list is like shown below, Find a node from where loop/cycle starts.
(In below example, it starts at Node 5).
We just saw that, loop in a linked list can be identified by,
1. Initializing 2 pointers(tortoise, hare) at start node and then
2. Moving tortoise pointer forward 1 node at a time and moving hare pointer forward 2 nodes at same
time.
In this way, if the linked list contains loop then tortoise and hare will meet at some node in
loop otherwise hare will reach NULL.
Now point is, how we will come to know the start node of a loop.
STEP 1: After finding the loop, both pointers are pointing to common node that is at meeting point
inside loop,
STEP 2: Now, move one pointer among them(say tortoise) to the head of list, keeping hare
pointer at the same position that is at meeting point inside loop.
STEP 3: Start moving both pointers one node at a time. The place they both will meet is the start
node of the loop/cycle.
How does the Algorithm work?
Lets understand with the help of example.
1. Consider the distance between start node of the list and start of loop node be "p" and
2. Consider the distance between start of loop node and the meeting point(node) of both pointers
be "q".
3. Consider the distance between the meeting point of both pointers and the start node of the loop
be "r".
Tortoise pointer was moving one node at a time and hare pointer was moving 2 nodes at same time.
So we can say, when tortoise pointer has moved distance "d"
then hare pointer has moved distance "2d".
From the above image, the length of loop is q+r.
When tortoise and hare meet, tortoise has covered distance d = p+q and hare has covered distance 2*d = p+q+r+q
2*d = p + q + r + q
2(p+q) = p + 2q + r
2p + 2q = p + 2q + r
p = r
(It means distance from head node to the start of loop node is same as distance between meeting point of the pointers to the start of loop node)
So this shows after getting meeting point, if one pointer is placed at the beginning of the list, then moving both pointer one node at a time then they will meet at the start of loop.
Identify start node of loop in Linked List. (in Java)
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 loop node, So that we can set it to NULL.
For identifying the previous node of loop node, we will keep the previousPointer pointing to just previous node of loop node.
CASE 2:
When the meeting node of both pointers in 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 last node of the linked list.
CASE 1:
When the meeting node of both pointers in loop is in-between the linked list, in this case, 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 list to NULL will work.
Program to Remove loop in linked list.
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();
}
}
}
You may also like to see
Convert Sorted Linked List to balanced BST
Clone Linked list in Java
Sort Linked list in Java
Find Nth node from last in a linked list
Count zeros in a row wise and column wise sorted matrix
When to use interface and abstract class in Java? what is the difference between them?
Advanced Multithreading Interview Questions In Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment