In this article, we will discuss an algorithm on how to find and break loop in a linked list. So, in a given linked list, check whether it contains the loop in it, if yes then find the Loop and break this loop. As know that, a singly linked list has several nodes, and each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node.
Algorithms related to the Singly Linked list
There are the following algorithms, we have discussed related to the singly linked list:
- Find the nth node from the end of a singly linked list
- Find the middle element in a linked list
- How to Reverse linked list in Java
- Delete given node from a singly linked list
- Remove Duplicates from the Unsorted Singly Linked list
- The singly linked list is palindrome without extra space
- How to Detect loop in a linked list
Find and Break loop in a linked list
Let’s see the following diagram of the singly linked list:
As you can see in the above diagram, loop in a linked list means the last node does not point to the null, instead it points to some node in the list. There are are several approaches to solve this problem.
Approach to find and break loop in a linked list
This is a very efficient approach to detect a loop in a linked list.
Step 1: Let’s take two pointers slow and fast.
Step 2: Intialize both pointers slow = head and fast = head.next.next.
Step 3: Navigate both pointers, the slow pointer moves one node at a time but fast pointer moves two nodes a time.
Step 4: If both pointers meet at some point, we have found the loop.
Step 5: Now find the loop length
Step 6: At the point where both pointers have met, stop one pointer and keep moving the another one
Step 7: When another pointer meets the first pointer, stop.
Step 8: Keep counting number of hops, that will your loop length
Step 9: Let’s break the loop
Step 10: Move one pointer by the loop length from the head of the linked list
Step 11: Another pointer fixes at the head and moves both pointers with normal speed.
Step 12: When ptr2.next = ptr1 pointer, set ptr2.next=null
Let’s see the complete code for this algorithm.
/**
*
*/
package com.dineshonjava.algo.linkedlist;
/**
* @author Dinesh.Rajput
*
*/
public class LoopInLinkedList {
public static void main(String[] args) {
Node head = new Node("1");
head.next = new Node("2");
head.next.next = new Node("3");
head.next.next.next = new Node("4");
head.next.next.next.next = new Node("5");
head.next.next.next.next.next = new Node("6");
head.next.next.next.next.next.next = new Node("7");
head.next.next.next.next.next.next.next = head.next.next;
findLoop(head);
display(head);
}
private static void findLoop(Node head) {
Node slow = head;
Node fast = head.next.next;
while(slow != null) {
if(slow == fast) {
System.out.println("Loop Found in Linked List");
int lengthLoop = findLength(slow, fast);
breakLoop(head, lengthLoop);
break;
}else {
slow = slow.next;
fast = fast.next.next;
}
}
}
private static int findLength(Node firstPtr, Node secondPtr) {
secondPtr = secondPtr.next;
int lengthLoop = 1;
while(secondPtr != firstPtr) {
lengthLoop++;
secondPtr = secondPtr.next;
}
System.out.println("Length of Loop is "+lengthLoop);
return lengthLoop;
}
private static void breakLoop(Node head, int lengthLoop) {
Node ptr1 = head;
Node ptr2 = head;
while(lengthLoop > 0) {
lengthLoop --;
ptr2 = ptr2.next;
}
while(ptr2 != ptr1) {
ptr2 = ptr2.next;
ptr1 = ptr1.next;
}
ptr2 = ptr2.next;
while (ptr2.next != ptr1) {
ptr2 = ptr2.next;
}
ptr2.next = null;
System.out.println("Loop breaks");
}
private static void display(Node head){
Node n=head;
while(n!=null){
System.out.print("->" + n.data);
n=n.next;
}
}
}
public class Node {
Node next;
String data;
public Node(String data) {
super();
this.data = data;
}
}
Run above program, you will get the following output:
Loop Found in Linked List Length of Loop is 5 Loop breaks ->1->2->3->4->5->6->7
In this example, we have written a program to find and break a loop in a linked list
Hope, you have understood this solution. Please share other solutions if you have. :).
Happy learning with us!!!.
