Find the Loop in a Linked list, find its length and Break the Loop

Objective: In a given linked list, check whether it contains the loop in it, if yes then find the Loop length and break the loop.

Loop in a linked list means the last node does not point to the null, instead it points to some node in the list.

Input: A Linked List

Output: Linked list contains loop or not, if yes its length and linked list after breaking the loop.

Example: 

Input : ->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30

here you can see that 30->40->50->60 are repeating ,that means it has a loop
Loop in a Linked List
Loop in a Linked List

Approach:

  • Find the Loop
  • Take two pointers, both starts from head
  • Move one pointer with normal speed and another with double speed
  • If both pointers meets at some point, we have found the loop
  • Now find the loop length
  • At the point where both pointers have met, stop one pointer and keep moving the another one
  • When another pointer meets the first pointer, stop.
  • Keep counting number of hops, that will your loop length
  • Now To break the loop
  • Move one pointer by the loop length
  • Now move both pointers with normal speed.
  • When secondpointer.next = first pointer, set secondpinter.next=null.

Complete Code:

//Find the Loop
//Take two pointers, both starts from head
//move one pointer with normal speed and another with double speed
//if both pointers meets at some point, we have found the loop
//Now find the loop length
//at the point where both pointers have met, stop one pointer and keep moving the nother one
//when another pointer meets the first pointer, stop.
//keep counting number of hops, that will your loop length
//Now To break the loop
//move one pointer by the loop length
//now move both pointers with normal speed.
//when secondpointer.next = first pointer, set secondpinter.next=null.
public class FindLoopInLinkedList
{ public LinkedListLoop a;
public int loopLength;
public void createLoop(){
a = new LinkedListLoop();
a.addAtEnd(10);
a.addAtEnd(20);
a.addAtEnd(30);
a.addAtEnd(40);
a.addAtEnd(50);
a.addAtEnd(60);
a.insertLoop(2);
a.displayLoop();
}
public void findLoop(){
Node ptrOne =a.head;
Node ptrTwo =a.head.next.next;
while(ptrOne!=null){
if(ptrOne!=ptrTwo){
ptrOne = ptrOne.next;
ptrTwo = ptrTwo.next.next;
}
else{
System.out.println("");
System.out.println("Loop Found–starts at " + ptrOne.data);
findLoopLength(ptrOne, ptrTwo);
breakLoop(ptrOne, ptrTwo);
break;
}
}
}
public void findLoopLength(Node one, Node two){
one = one.next;
loopLength = 1;
while(one!=two){
one = one.next;
loopLength++;
}
System.out.println("Loop length is " + loopLength);
}
public void breakLoop(Node one, Node two){
one = one.next;
while(one.next!=two){
one = one.next;
}
one.next = null;
System.out.println("Loop breaks");
a.display();
}
public static void main (String[] args) throws java.lang.Exception
{
FindLoopInLinkedList i = new FindLoopInLinkedList();
i.createLoop();
i.findLoop();
}
}
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
class LinkedListLoop{
public Node head;
public LinkedListLoop(){
head=null;
}
public void addAtEnd(int data){
Node n = new Node(data);
if (head==null){
n.next = head;
head = n;
}
else{
Node currNode = head;
while(currNode.next!=null){
//System.out.print("—->" + currNode.data);
currNode = currNode.next;
}
currNode.next = n;
}
}
public void insertLoop(int index){
Node endNode = head;
while(endNode.next!=null){
//System.out.print("—->" + currNode.data);
endNode = endNode.next;
}
Node indexNode = head;
while(index!=0){
indexNode = indexNode.next;
index;
}
endNode.next = indexNode;
}
public void displayLoop(){
System.out.println("");
Node currNode = head;
int cnt = 15;
while(cnt!=0){
System.out.print("->" + currNode.data);
currNode=currNode.next;
cnt;
}
}
public void display(){
System.out.println("");
Node currNode = head;
while(currNode!=null){
System.out.print("->" + currNode.data);
currNode=currNode.next;
}
}
}


Output:

->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30
Loop Found--starts at 30
Loop length is 4
Loop breaks

->10->20->30->40->50->60