Detect Loop in linked list Java

PROGRAM TO DETECT AND REMOVE LOOP IN A LINKED LIST

class LinkedList {

 

    static Node head;

 

    static class Node {

 

        int data;

        Node next;

 

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

 

    // Function that detects loop in the list

    void detectAndRemoveLoop(Node node)

    {

 

        // If list is empty or has only one node

        // without loop

        if (node == null || node.next == null)

            return;

 

        Node slow = node, fast = node;

 

        // Move slow and fast 1 and 2 steps

        // ahead respectively.

        slow = slow.next;

        fast = fast.next.next;

 

        // Search for loop using slow and fast pointers

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

            if (slow == fast)

                break;

 

            slow = slow.next;

            fast = fast.next.next;

        }

 

        /* If loop exists */

        if (slow == fast) {

            slow = node;

            while (slow.next != fast.next) {

                slow = slow.next;

                fast = fast.next;

            }

 

            /* since fast->next is the looping point */

            fast.next = null; /* remove loop */

        }

    }

 

    // Function to print the linked list

    void printList(Node node)

    {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

 

    // Driver code

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(50);

        list.head.next = new Node(20);

        list.head.next.next = new Node(15);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(10);

 

        // Creating a loop for testing

        head.next.next.next.next.next = head.next.next;

        list.detectAndRemoveLoop(head);

        System.out.println("Linked List after removing loop : ");

        list.printList(head);

    }

}




OUTPUT

Linked List after removing loop 
50 20 15 4 10 

CREDITS: https://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/