# 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.

- Start traversing the list.
- Put one by one all the node addresses in a
**Hash Table**. - If NULL reaches at any point then return false.
- 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:

## Leave a Reply