Linked list - If loop exists get starting of loop - Java
public class Cirsle {
/**
* @param args
*/
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n3);
Node nth = circle(n1);
System.out.println(nth.getData());
}
private static Node circle(Node root){
Node slwPtr = null;
Node fasPtr = null;
boolean loopExists = false;
if(root != null){
slwPtr = root;
fasPtr = slwPtr;
}
while(fasPtr.getNext() != null && fasPtr.getNext().getNext() != null){
slwPtr = slwPtr.getNext();
fasPtr = fasPtr.getNext().getNext();
if(slwPtr == fasPtr){
loopExists = true;
break;
}
}
if(loopExists){
slwPtr = root;
while(slwPtr != fasPtr){
slwPtr = slwPtr.getNext();
fasPtr = fasPtr.getNext();
}
return slwPtr;
}
return null;
}
}
-----------------------------------------------------
o/p: 3
/**
* @param args
*/
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n3);
Node nth = circle(n1);
System.out.println(nth.getData());
}
private static Node circle(Node root){
Node slwPtr = null;
Node fasPtr = null;
boolean loopExists = false;
if(root != null){
slwPtr = root;
fasPtr = slwPtr;
}
while(fasPtr.getNext() != null && fasPtr.getNext().getNext() != null){
slwPtr = slwPtr.getNext();
fasPtr = fasPtr.getNext().getNext();
if(slwPtr == fasPtr){
loopExists = true;
break;
}
}
if(loopExists){
slwPtr = root;
while(slwPtr != fasPtr){
slwPtr = slwPtr.getNext();
fasPtr = fasPtr.getNext();
}
return slwPtr;
}
return null;
}
}
-----------------------------------------------------
o/p: 3
Comments
Post a Comment