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.
There are the following algorithms, we have discussed related to the singly 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.
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.
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!!!.
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…