Java Program to Detect a Loop in a Linked List

This Java program demonstrates how to detect if a given singly linked list contains a loop or cycle. A loop in a linked list occurs when a node’s next pointer points back to a previous node, forming a cycle. The algorithm used here is known as Floyd’s Cycle Detection Algorithm or the “Tortoise and Hare” algorithm.

Program Structure

The program consists of the following components:

• Node Class: This class represents a single node in the linked list. Each node contains an integer value and a reference to the next node.
• LinkedList Class: This class contains the methods to create a linked list, add elements to it, and the method to detect a loop.
• Main Method: The entry point of the program where a linked list is created, a loop is optionally introduced, and the detection method is invoked.

Java Code

public class LinkedListLoopDetection {

    // Node class representing each element in the linked list
    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // LinkedList class containing methods to detect a loop
    static class LinkedList {
        Node head;

        // Method to add a node to the end of the list
        public void add(int data) {
            Node newNode = new Node(data);
            if (head == null) {
                head = newNode;
            } else {
                Node current = head;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = newNode;
            }
        }

        // Method to detect if there is a loop in the linked list
        public boolean hasLoop() {
            Node slow = head;
            Node fast = head;

            while (fast != null && fast.next != null) {
                slow = slow.next;         // Move slow pointer by 1 step
                fast = fast.next.next;    // Move fast pointer by 2 steps

                if (slow == fast) {       // If they meet, loop is present
                    return true;
                }
            }

            return false;  // If we exit the loop, no cycle was detected
        }
    }

    // Main method to test the loop detection
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Creating a linked list
        list.add(10);
        list.add(20);
        list.add(30);
        list.add(40);
        list.add(50);

        // Introducing a loop for testing purposes
        list.head.next.next.next.next.next = list.head.next;

        // Checking if the linked list has a loop
        if (list.hasLoop()) {
            System.out.println("Loop detected in the linked list.");
        } else {
            System.out.println("No loop detected in the linked list.");
        }
    }
}

    

Explanation

• Node Class: This class defines a node in the linked list. Each node holds an integer data and a reference to the next node.
• LinkedList Class:
  • add(int data): This method adds a new node with the given data to the end of the list. If the list is empty, the new node becomes the head.
  • hasLoop(): This method detects the presence of a loop using two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps. If they ever meet, a loop exists. If the fast pointer reaches the end of the list, no loop exists.
• Main Method: In the main method, a linked list is created and populated with values. A loop is introduced manually by making the last node point to one of the previous nodes. The hasLoop() method is then called to check for a loop, and the result is printed.

Conclusion

Floyd’s Cycle Detection Algorithm is an efficient way to detect a loop in a linked list with a time complexity of O(n) and a space complexity of O(1). It is widely used in many practical scenarios involving linked lists.