Sunday, August 9, 2015

Detecting the loops in a linked list

Hello Friends today I want to take one of the question that one of my friend asked me which he faced in an interview.

How would you detect whether the linked list has the loop or not?

Let us take a basic example, so assume you have the linked list like that looks like this:

A -> B -> C -> D ->B

Now if you look at the list you find out that the last node is pointing towards B. So now the question is how would you find whether the list has a loop or not.

For this problem there are some solutions, one of them is Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

The algorithm's idea is that, maintains 2 pointers and move with them with different speeds, one fast and one slow, if there is a loop, one time they will definitely meet.

Going forward with this idea in mind, let us see the program.


boolean hasLoop(Node first) {
    if (first == null) // list does not exist..so no loop either.
        return false;
    Node slow, fast; // create two references.
    slow = fast = first; // make both refer to the start of the list.
    while (true) {
        slow = slow.next;          // 1 hop.
        if (fast.next != null)
            fast = fast.next.next; // 2 hops.
        else
            return false;          // next node null => no loop.

        if (slow == null || fast == null) // if either hits null..no loop.
            return false;
        if (slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

Now the other problem is to know the start of the loop. For that we follow:

Step1: Proceed in the usual way u'll use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.

Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps u make and when they both meet again, the count will give u the length of the loop.(This is same as counting the number of elements in a circular link list.)

Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it'll be the start of the loop. (This is same as finding the nth element from the end of the link list.)

Working code here

public class LoopInLinkedList {

    static class Node {
        public String info;
        public Node next;
        @Override
        public String toString() {
            return "Node [info=" + info + ", next=" + next.hashCode() + "]";
        }
    }
    public static void main(String[] args) throws Exception {

        Node n1 = new Node();
        n1.info = "A";
        Node n2 = new Node();
        n2.info = "B";
        Node n3 = new Node();
        n3.info = "C";
        Node n4 = new Node();
        n4.info = "D";
        Node n5 = new Node();
        n5.info = "E";
        Node n6 = new Node();
        n6.info = "F";
        Node n7 = new Node();
        n7.info = "G";
        Node n8 = new Node();
        n8.info = "H";

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n2;

        detectLoop(n1);
    }
    public static boolean detectLoop(Node start) throws Exception {
        Node slow = start;
        Node fast = start;
        while (slow !=null && fast != null) {
            slow=slow.next;
            fast=fast.next.next;
            if (fast == slow) {
                int k = getLengthOfLoop(fast);
                Node startOfLoopNode = detectLoopStart(start, k);
                System.out.println("Length of the loop is " + k);
                System.out.println("Start of the loop is " + startOfLoopNode);
                return true;
            }
        }
        return false;
    }
    private static int getLengthOfLoop(Node loopNode) throws Exception {
        Node ptr = loopNode;
        int k=0;
        while ((ptr=ptr.next)!=loopNode) {
            k++;
        }
        return k+1;
    }
    private static Node detectLoopStart(Node start, int k) throws Exception {
        Node ptr1 = start;
        Node ptr2 = start;
        while (k-->0 && (ptr1 = ptr1.next)!=null);
        while ((ptr1=ptr1.next)!=null && (ptr2=ptr2.next)!=null && ptr1 != ptr2);
        return ptr1;
    }
}

No comments:

Post a Comment