There are many ways of storing data when writing a computer program especially when it's a group of data that share the same property. Like the data of students under the age of 12 or People who love same category of movies.
This can be store as an array or a slice into the memory but sometime you just want some that is very simple to work with when the data get massively large to go through. Cases like this are when linked list comes to play. It essentially just a sequence elements where one element links to the next element.


package floyd;
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;
}
}
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;
}
}
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;
}
}
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;
}
}

Distance traveled by fast fast pointer(Hare) before meeting =(𝑥+𝑦+𝑧)+𝑦 = x + 2y + z
Since fast pointer(Hare) travels double the speed of the slow pointer(Tortoise) and time is constant for both when the reach the meeting point. So by using simple speed, time and distance relation (slow pointer(Tortoise) traveled half the distance): For this case we will take distance moved by the fast pointer (Hare) as i and the distance moved by the slow pointer(Tortoise) as j.
Therefore:
2 * j = i
2(x + z) = x + 2z + (y - z)
2x + 2z = x + 2z + (y - z)
x = z
Hence by moving slow pointer(Tortoise) to starting of the linked list, and making both slow pointer and fast pointer(Hare) to move one node at a time, they both have same distance to cover. They will reach at the node where the loop starts in the list.
2 * j = i
2(x + z) = x + 2z + (y - z)
2x + 2z = x + 2z + (y - z)
x = z
Thanks!
Your feedback helps us improve tutorials.
No comments:
Post a Comment