Input:
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
^ |
| |
+------------------------+
Output: 3 (because loop starts at Node 3)
Finding starting node of loop is very easy if you get the solution properly.
Lets try to understand the same, Before jumping to the actual solution lets try to understand few basic calculations.
Me and my friend Khyati daily go for jogging, we both enter the jogging track and our starting point from which we start the jogging is same.
Khyati is more energetic then me, so she runs fast that is twice then me.
So, when I complete half jogging track, she is done and reached at starting point.
Now, when I start from half way to complete the jogging, khyati travelled twice and again reached the start location.
From this, I can say that when person start from same location in a circular track and if one of them run in 2x speed then they both will
meet at the same place they started.
A,B ---> starting point, lets see where A and B meets if B runs in 2x speed then A.
*
* *
* *
* *
*
*
* *
A *
* *
B
B
* *
* *
* *
A
*
* *
* A
* *
B
A,B --------> A and B meet at same place they originally started.
*
* *
* *
* *
*
Now, lets try to understand, where A and B will meet if the starting location of A and B in circular jogging track is different.
A --------> starting place of A
*
* *
B-----*---------> starting place of B.
* *
*
Lets consider the distance between A and B initially is m.
Now, if the length of jogging track is n then B is at position n - m
Now,
when A reaches to B position that is at n-m position,
B will advance to m + 2(n-m) position.
[m = position where B started.(taken into consideration because when A is at starting point of track, B already started from m length ahead of A)
2(n-m) = double the length A traveled.]
=m + 2(n-m)
=m + 2n - 2m
=m + 2n - 2m
=2n - m
=n - m (2 is removed because the path is circular and we are not concerned about the number of complete rounds B has took more after which they meet; we are just interested in the position where they meet)
So this says, when A reaches n-m, B will also reach n-m position (of course B took 2 complete rounds of track and then came at place n-m whereas A just came to n-m position moving one node at at time, but we are only interested in getting the meeting point, so ignore the number of complete rounds taken by B)
Meeting point of A and B is the point where B started ie n-m.
Now, if we come to our original problem of Linklist which contains loop in it and need to find node at the start of the loop.
A,B
* * * * ----------Collision point
* *
* *
*
* A B * ----------Collision point
* *
* *
*
* * A * ----------Collision point
* B
* *
*
* * * A ----------Collision point
* *
* *
B
Now, when A reaches the collision point (say distance k from start node), then distance travelled by the B is double then A that is 2k,
it means B is K node inside the loop,
At this time distance between start node and A is same as distance between A and B (as B travelled A+A).
Considering this situation, where A is at start of the loop and B is k node ahead of A, find when A and B will meet, we already solved this above
and it will meet at the B start position ie at (n - k) as B position is n - k nodes inside the loop.
Also, we know n-k nodes is actually K nodes away from A start position that is at loop start.
So, as discussed distance between start node and A (at loop start) is same as distance between A and B (k).
Now at this point where both pointers meet at n-k place ie K place far from loop start point.
we can move the A pointer back to first position and then advance both A and B one at a time, they will surely meet at loop start point as both are at equal distance.
=================================================================================
Let us understand in other way
A,B x
* * * * ----------------start of loop node
* * y
z * * ----------Collision point
*
let us assume that A and B meet at Collision point.
say distance from start to start of loop node = x
say distance from start of loop node to Collision point = y
say distance from Collision point to start of loop node = z
so at the time of collision A will travel a distance of x+y
and B will travel a distance of x+y+z+y
Also, y+z is loop length.
So before meeting at Collision point, B might have travel the loop twice thrice etc, so the formula should be,
= x+y+z+y
= x+nl+y (n is number of times it travel loop length l)
But we can ignore the nl as we are only interested at point they meet and not interested in number of time B
travelled through loop to meet A.
So A distance is d = x + y
and B distance is 2d = x + y + z + y = x + 2y + z
2d = x+2y+z (but d = x + y)
2(x+y) = x+2y+z
2x + 2y = x+2y+z
2x - x + 2y - 2y = z
x = z
This proves that x distance is same as z distance.
which means when A and B meets at Collision point and if we keep one pointer to start node and one pointer at
Collision point and start forwarding one by one then they both will meet at collision point as x = z
package linkedlist.singly;
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(n4);
//Check If loop is Present
System.out.println(isLoopPresent(g.startNode));
//Get the start Node of a loop
Node temp = g.getStartNodeOfLoopInLinklist(g.startNode);
if(temp==null){
System.out.println("Loop not present");
}else{
System.out.println(temp.getData());
}
//Detect and Remove Loop in a Linked List
Node newStart = removeLoop(g.startNode);
g.printList(newStart);
}
private static boolean isLoopPresent(Node startNode){
Node slowPointer=startNode;
Node fastPointer=startNode;
while(fastPointer!=null && fastPointer.getNext()!=null){
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
if(slowPointer==fastPointer)
return true;
}
return false;
}
private Node getStartNodeOfLoopInLinklist(Node startNode){
Node slowPointer=startNode;
Node fastPointer=startNode;
while(fastPointer!=null && fastPointer.getNext()!=null){
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
if(slowPointer==fastPointer){
slowPointer = startNode;
while(slowPointer!=fastPointer){
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
}
return slowPointer;
}
}
return null;
}
private static Node removeLoop(Node startNode) {
Node slowPointer=startNode;
Node fastPointer=startNode;
while(fastPointer!=null && fastPointer.getNext()!=null){
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
if(slowPointer==fastPointer){
slowPointer = startNode;
while(slowPointer.getNext()!=fastPointer.getNext()){
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
}
fastPointer.setNext(null);
}
}
return startNode;
}
private void printList(Node startNode){
while(startNode!=null){
System.out.print(startNode.getData() + " " );
startNode=startNode.getNext();
}
}
}
No comments:
Post a Comment