1. Introduction

A common problem when dealing with linked lists is detecting if the list contains a loop. A loop in a linked list means that visiting nodes in a sequence, we will eventually revisit a node. This can cause infinite traversals and other unexpected behaviors. In this post, we will discuss how to detect a loop in a linked list using Java.

2. Program Steps

1. Initialize two pointers, slow and fast.

2. Move slow one step at a time and fast two steps at a time.

3. If there’s a loop, the fast pointer will eventually meet the slow pointer.

4. If the fast pointer reaches the end of the list (i.e., it becomes null), then there’s no loop.

3. Code Program

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Function to detect a loop in the linked list
    public boolean detectLoop() {
        Node slow = head, fast = head;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    // Function to add a new node at the end of the list
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

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

        list.append(10);
        list.append(20);
        list.append(30);
        list.append(40);

        // Creating a loop for testing
        list.head.next.next.next.next = list.head;

        if (list.detectLoop())
            System.out.println("Loop found");
        else
            System.out.println("No Loop found");
    }
}

Output:

Loop found

4. Step By Step Explanation

1. A Node class is created to represent the elements in our linked list.

2. The LinkedList class provides the methods to add nodes and to detect loops.

3. The detectLoop method uses the Floyd's Cycle-Finding Algorithm or Tortoise and the Hare approach.

4. Two pointers (slow and fast) are initialized to the head of the list.

5. The slow pointer moves one step at a time while the fast pointer moves two steps.

6. If there's a loop, these two pointers will eventually meet.

7. If either pointer becomes null, then there's no loop in the list.

8. In the main method, we create a loop artificially by setting the next of the last node to the head of the list.

9. We then call detectLoop to check if there's a loop, and the result is printed out.

This approach allows us to detect loops without using any additional space and in linear time.