Java Program to detect a Loop in a Linked List

In this tutorial, we will see how to detect a loop in a linked list in java. LinkedList is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays. But before moving further, if you are not familiar with the concept of the linked list in java, then do check the article on Linked List in Java.

Input: Enter the Linked List elements: 6 7 8 4 5

Output: Loop Found

This can be done by using the following methods:

Approach 1: Using Hash-Set

Approach 2: Without Using Hash-Set

Let us look at each of these approaches for a better understanding.

Program 1: Detect a Loop in a Linked List

In this program, we will see how to detect a loop in a linked list using hashing approach.

Algorithm:

1. Start
2. Create a linked list.
3. Add elements to the list.
4. Use a boolean method to check if a loop exists or not.
5. Use a HashSet for the same.
6. Traverse the list one by one and keep putting the node addresses in a Hash Table.
7. At any point, if null is reached then return false.
8. If the next current node points to any of the previously stored nodes in HashSet then return true.
9. Display the result.
10. Stop

Let us look at the below example for a better understanding of the above algorithm.

// Java program to detect loop in a linked list
import java.util.*;
public class LinkedList 
{
	static Node head; // head of list
	/* Linked list Node*/
	static class Node {
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	static public void add(int newData)
	{
		Node newNode = new Node(newData);
		newNode.next = head;
		head = newNode;
	}
	static boolean checkLoop(Node n)
	{
		HashSet<Node> hset = new HashSet<Node>();
		while (n != null) {
			if (hset.contains(n))
				return true;
			hset.add(n);
			n = n.next;
		}
		return false;
	}
	//Driver program
	public static void main(String[] args)
	{
		LinkedList ll = new LinkedList();
		ll.add(8);
		ll.add(12);
		ll.add(15);
		ll.add(21);
		ll.head.next.next.next.next = ll.head;
		if (checkLoop(head))
			System.out.println("Loop found");
		else
			System.out.println("No Loop found");
	}
}

Loop found

Program 2: Detect a Loop in a Linked List

In this program, we will see how to detect a loop in a linked list.

Algorithm:

1. Start
2. Create a linked list.
3. Create a linked list.
4. Add elements to the list.
5. Use a boolean method to check if a loop exists or not.
6. Declare a temp variable and initialize it to 0.
7. Traverse the linked list and keep marking visited nodes.
8. If a visited node is found again then there is a loop.
9. Display the result.
10. Stop

Let us look at the below example for a better understanding of the above algorithm.

// Java program to detect loop in a linked list
import java.util.*;
public class Main
{
    static class Node
    {
       int data;
       Node next;
       int temp;
    };
    static Node add(Node newHead, int newData)
    {
        Node newNode = new Node();
        newNode.data = newData;
        newNode.temp = 0;
        newNode.next = newHead;
        newHead = newNode;
        return newHead;
    }
    static boolean detect(Node n)
    {
        while (n != null)
        {
            if (n.temp == 1)
               return true;
            n.temp = 1;
            n = n.next;
        }
        return false;
    }
    // Driver code
    public static void main(String[] args)
    {
        Node head = null;
        head = add(head, 20);
        head = add(head, 4);
        head = add(head, 15);
        head = add(head, 10);
        head.next.next.next.next = head;
        if (detect(head))
           System.out.print("Loop found");
        else
           System.out.print("No Loop found");
    }
}

Loop found