package linkelist.example;
public class LinkedListDetectLoop {
private Node startNode;
public static void main(String[] args) {
LinkedListDetectLoop detectLoopInLinkedList = new LinkedListDetectLoop();
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 slowPointer is at starting location.
Node fastPointer = startNode; // Initially fastPointer is at starting location.
while (fastPointer != null && fastPointer.getNext() != null) { // If fastPointer get NULL, it means there is no
// Loop in Linked list.
slowPointer = slowPointer.getNext(); // slowPointer moving one node at at time
fastPointer = fastPointer.getNext().getNext(); // fastPointer moving two nodes at at time
if (slowPointer == fastPointer) // if slowPointer and fastPointer meets, it means linked list contains loop.
return true;
}
return false;
}
}
package linkelist.example;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;
}
}
Loop is present in list
No comments:
Post a Comment