Loop detection in a linked list

In this post, we will discuss about the different algorithm for loop detection in a linked list.

Before writing the logic for loop detection in a linked list, we should understand the type and properties of the input parameter of this problem. We need a composite linked list consist of a singly linked list connected with a singly circular linked list. Below is the node structure of a given composite linked list.

 

To form a composite linked list, we will create one instance of SinglyLinkedList and one instance of SinglyCircularLinkedList then add the singly circular linked list to singly linked list. Refer the SinglyLinkedList.java and SinglyCircularLinkedList.java.

Now, we are going to discuss two techniques by which we can detect the loop in a given composite linked list and count the number of nodes in loop.

  1. Hashing : In Hashing technique, put all the node addresses into a HashSet and check if the node is available in HashSet. If yes, then loop detected in a composite linked list and stop moving to the next node. If no, then add the address into HashSet and move to the next node.This technique is good in case of less number of nodes in composite linked list, but if number of nodes in composite linked list is very huge, performance will be poor because we need to traverse through all the nodes to check the loop.
  2. Floyd’s loop detection algorithm: According to Floyd’s loop detection algorithm, if slow moving pointer and fast moving pointer meet at some common point then there is a loop in a linked list. Definition of slow moving pointer and fast moving pointer refers, when a pointer move to the next consecutive node, that is called slow moving pointer. When a pointer skip the next consecutive node and move to the next of next node, that is called fast moving pointer.

 

Below is the code snippet to detect loop in a linked list using Hashing and Floyd’s loop detection algorithm.

Node.java

 

SinglyLinkedList.java

 

SinglyCircularLinkedList.java

 

LoopDetectionInLinkedListTest.java

 

 

Console Output:

Loop Detected using Hashing: true

**********FLOYD LOOP DETECTION**********
Loop Found
Number of nodes present in Loop: 4


 

Hope you liked this post. Please leave your comments or suggestions.

Cheers 🙂

Top