Find Loop in a Linked List

 Problem Statement

In this problem, we are given a linked list with a loop. We have to find the first node of the loop in the linked list.

Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Suppose the given list is:

• According to the problem statement, we need to find the starting node of the loop.
• From the linked list, we can see that there is a loop in the linked list starting at node with value 3 and containing 3 nodes 3, 5, and 7. The last node of the loop points back to the first node of the loop.
• As node with value 3 is the first node of the loop, so we will return 3 as output.

Approach and Algorithm (Floyd’s Cycle Detection)

Our approach will be simple:
1) Firstly, we have to detect the loop in the given linked list.

• For detecting a loop in any linked list, we know the most efficient algorithm is the Floyd Cycle detection Algorithm.

2) In Floyd's cycle detection algorithm, we initialize 2 pointers, slow and fast.

• Both initially point to the head of the list.
• The slow pointer jumps one place and the fast pointer jumps 2 places.
• The node at which the slow and fast pointer meet is a loop node.

3) Now, after finding the loop node:

• We will make 2 pointers ptr1 and ptr2, which will point to that loop node.
• We will also initialize a variable to find the length of the loop. Now, how will we find the length of this loop?
  • ptr2 will be fixed, and we will increment ptr1 till it meets ptr2. As both are at the same position currently, when ptr1 will meet ptr2, the whole loop would've been traversed, and we will get the length k.

4) Now, as we have the length of the loop, we will make ptr1 and ptr2 point to the head again.

5) Now, we will shift ptr2 by k places.

6) After shifting, we will move both ptr1 and ptr2 simultaneously (taking 1 jump). The node at which ptr1 and ptr2 will meet will be the first node of the loop.

7) After finding the first node of the loop, we will return it.

public class LinkedListWithLoop {

    public static void main(String args[]) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node2;

        Node output = findFirstNodeInLoop(node1);
        System.out.println("Loop Node-->" + output.getData());

        int length = findLengthOfTheLoop(node1);
        System.out.print("Length-->" + length);

    }

    /**
     * First Find the loop, then move the slow to head and move the slow and fast by 1 until they meet,
     * where they meet is the first node of the loop.
     *
     * @param head
     * @return
     */
    public static Node findFirstNodeInLoop(Node head) {
        if (head == null || head.next == null) {
            return null;
        }

        Node slow = head;
        Node fast = head;

        slow = slow.next;
        fast = fast.next.next;

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

        }

        if (slow != fast) {
            return null;
        }

        slow = head;

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

        return slow;

    }

    public static int findLengthOfTheLoop(Node head) {
        if (head == null || head.next == null) {
            return 0;
        }

        Node slow = head;
        Node fast = head;

        slow = slow.next;
        fast = fast.next.next;

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

        }

        if (slow != fast) {
            return 0;
        }

        slow = slow.next;
        int k = 1;

        while (slow != fast) {
            slow = slow.next;
            k++;
        }

        return k;

    }
}