In this article, we will discuss an algorithm on how to detect a 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 length. 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
Detect 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 1: Using Hashing
Navigate the linked list and put each node to the HashSet if the node is not present in the HashSet if node is present in the HashSet that means the given singly linked list has a loop.
Approach 2: Using Fast and Slow pointers
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, 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
Let’s see the complete code for this algorithm.
package com.dineshonjava.algo.linkedlist;
/**
* @author Dinesh.Rajput
*
*/
public class Node {
Node next;
String data;
public Node(String data) {
super();
this.data = data;
}
}
Code for loop detection in the linked list
LoopInLinkedList.java
/**
*
*/
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);
}
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);
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;
}
}
Run above program, you will get the following output:
Loop Found in Linked List Length of Loop is 5
In this example, we have written a program to detect a loop in a linked list
Hope, you have understood this solution. Please share other solutions if you have. :).
Happy learning with us!!!.
