Detect a loop in a LinkedList in Java

LinkedList is a data structure which many of you are dealing with most of the time. This data structure makes the addition and deletion of data an easy task. Here I am with a very different problem of LinkedList which many of you may have seen. The task here is to find a loop in a LinkedList.

How to detect a loop in a LinkedList in Java?

There is a simple method to check whether a linked list has loop or not. Take a fast pointer and a slow pointer. Put a loop till fast pointer is not null. If there is a loop in the linked list then the slow pointer and fast pointer will meet once.

There is an efficient method to solve this problem with the help of Hashing. Since hashing is a very efficient way to solve some problems because it solves the problem in one traverse which reduces the time complexity of the problem and a good programmer always looks for a solution which is optimized.

The following are the steps to solve this problem using Hashing.

1. Start traversing the list.
2. Put one by one all the node addresses in a Hash Table.
3.  If NULL  reaches at any point then return false.
4. If next of the current node is pointing to any of the nodes which were stored in Hash then return true.

Here is the Java code:-

import java.util.*; 
  
public class Loop { 
  
    static Node head;  // head of list 
   
    static class Node { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    // append a new Node  
   public void append(int newdata) {
Node newnode = new Node( newdata);
if(head==null){
  head=newnode;
  return;
}
newnode.next=null;
Node last=head;
while(last.next!=null) {
  last=last.next;
}
last.next=newnode;
return;	
}
    /*  Function that returns true if there is a loop in linked 
     list else returns false. */
    static boolean detectLoop(Node head) 
    { 
        HashSet<Node>  hs= new HashSet<Node>(); 
        while (head != null) { 
            /* If we are already having this node 
            in the Hashmap  then it means there is a loop */
            if (hs.contains(head)) 
                return true; 
  
            /* Here  if we see the node for 
             the first time then  insert it in Hashtable (hs) */
            hs.add(head); 
  
            head = head.next; 
        } 
  
        return false; 
    } 
  
    // main function
    public static void main(String[] args) 
    { 
        Loop llist = new LinkedList(); 
  
        llist.append(20); 
        llist.append(4); 
        llist.append(15); 
        llist.append(10); 
  
        // making loop  
        llist.head.next.next.next.next = llist.head; 
  
        if (detectLoop(head)) 
            System.out.println("Loop found"); 
        else
            System.out.println("No Loop found"); 
    } 
} 

Output:

Loop found

The time complexity of this solution is: O(n)

Since for testing, I have made a loop in a linked list so the output is showing Loop found. Hence, by solving the problem through hashing we came up with an efficient solution and able to detect a loop in a LinkedList in Java.

Hope you find the solution useful.

Also, read:

• Method to reverse a LinkedList in Java