Remove a loop in a linked list

In this tutorial, we will see java program to remove a loop in linked list

In this code,If a loop is detected, we use another pointer to find the starting point of the loop and remove the loop.

The detectAndRemoveLoop method uses two pointers slow and fast to traverse the linked list. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If there is a loop in the linked list, the fast pointer will eventually catch up to the slow pointer.

Once the loop is detected, we use another pointer to find the starting point of the loop. To do this, we move one pointer to the head of the linked list and keep the other pointer at the point where the slow and fast pointers meet. We then move both pointers one node at a time until they meet at the starting point of the loop. Finally, we remove the loop by setting the next pointer of the node where the fast pointer is to null.

class LinkedList {
    static class Node {
        int data;
        Node next;

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

    Node head;

    // Function to detect and remove a loop in a linked list
    public void detectAndRemoveLoop() {
        if (head == null || head.next == null) {
            return;
        }

        Node slow = head;
        Node fast = head;

        // Move slow and fast pointers until they meet at a common point
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                break;
            }
        }

        // If loop exists, find the starting point of the loop
        if (slow == fast) {
            slow = head;
            while (slow.next != fast.next) {
                slow = slow.next;
                fast = fast.next;
            }
            fast.next = null; // Remove the loop
        }
    }

    // Utility function to create a linked list
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Utility function to print the linked list
    public void printList() {
        Node node = head;

        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }

        System.out.println();
    }
}