Write a Java Program to Detect loop in a LinkedList

In Java, a linked list is a data structure consisting of a sequence of nodes, where each node stores a reference to an object and a reference to the next node in the list.

A loop in a linked list occurs when a node is visited more than once while traversing the list.

Detecting a loop in a linked list is an important task in data structure and algorithmic programming.

In this tutorial, we will discuss how to detect a loop in a linked list using Java programming.


The algorithm for detecting a loop in a linked list is called the “Floyd’s cycle-finding algorithm.”

This algorithm involves the use of two pointers, one that moves at a pace of one node per iteration (slow pointer) and another that moves at a pace of two nodes per iteration (fast pointer).

If the linked list contains a loop, the fast pointer will eventually catch up to the slow pointer.

If the linked list does not contain a loop, the fast pointer will reach the end of the list and the algorithm will terminate.

Here’s the Java code to implement the Floyd’s cycle-finding algorithm:

javaCopy codeclass Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    // Function to detect loop in a linked list
    boolean detectLoop() {
        Node slow = head;
        Node fast = head;

        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // If slow and fast pointers meet at some point
            // then there is a loop in the linked list
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    // Function to add a new node at the beginning of the linked list
    void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    public static void main(String args[]) {
        LinkedList llist = new LinkedList();

        // Creating a linked list with a loop
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);

        // Creating a loop in the linked list
        llist.head.next.next.next.next = llist.head;

        boolean loop_present = llist.detectLoop();
        System.out.println("Loop present: " + loop_present);
    }
}

In this code, the Node class represents a single node in the linked list, and the LinkedList class represents the linked list itself.

The detectLoop() function implements the Floyd’s cycle-finding algorithm to detect a loop in the linked list.

The push() function adds a new node at the beginning of the linked list.

The main() function creates a linked list with a loop and calls the detectLoop() function to detect the loop.


In conclusion, detecting a loop in a linked list is a crucial operation in data structure and algorithmic programming.

The Floyd’s cycle-finding algorithm is an efficient and easy-to-implement algorithm to detect a loop in a linked list.

The Java code presented in this article demonstrates how to implement the Floyd’s cycle-finding algorithm to detect a loop in a linked list.