Thursday, December 25, 2014

An algorithm for returning the node at the beginning of a loop in a singly linked list.

Q. Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.

DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.

EXAMPLE

Input: A -> B -> C -> D -> E -> C (the same C as earlier)

Output: C

Methods:

#1. Use a Set to record every node that you visit. When a node that is already present in the list is encountered, the is the beginning of the loop. If pointer encounters null, no loop is present.

#2. Consider two pointers p1 and p2. p2 travels 2 nodes at a time, p1 travels 1 node at a time. Let them meet (if there is a loop, they will surely meet but if there isn't the fast node will encounter a null). Now that they have met, set p1 to head of the list. 

Now let p1 and p2 travel 1 node at a time. The point at which they meet again is the start of the loop. Now we just return that point.


Why does this happen?

Consider the case shown above. When P1 reaches the node at the head of the loop, it has hopped 4 times while P2 has hopped 8 times. Now if we put P1 back to the head of the linked list and make it go one node at a time, while we make P2 go reverse 1 node at a time they will meet at the start of the loop again (since P2 has travelled 2K-K = K more nodes, if P1 starts again from the head, and P2 rolls back, they meet at the start of loop after hopping 4 times.). The point where P1 and P2 meet is the point where this situation is reversed, now instead of P2 travelling back, it travels to the front to meet P1 at the start of the loop again if P1 had to begin travelling from the head of the linked list.

Source:

import java.util.HashSet;

public class Code{
    
    //Method 1
    public static <T> LinkedList.Node returnLoopStartNode(LinkedList<T> ll){ 
        HashSet<LinkedList.Node> record = new HashSet<>();
        LinkedList<T>.Node p = ll.head; 
        while(p!=null){
             if(!record.contains(p))record.add(p);
             else return p;
             p = p.next;
        }
        //No cycle here.
        return null;
    } 
    
    //Method 2 (Preferred)
    public static <T> LinkedList.Node returnLoopStartNodeM2(LinkedList<T> ll){
        LinkedList.Node p1 = ll.head, p2 = ll.head;
        if(p2.next!=null && p2.next.next!=null)p2 = p2.next.next;else return null;//No cycle
        p1 = p1.next;
        while(p1!=p2){
            p1 = p1.next;
            if(p2.next!=null && p2.next.next!=null) p2 = p2.next.next;
            else return null;//No cycle
        } 
        p1 = ll.head;
        while(p1!=p2){p1 = p1.next;p2 = p2.next;}
        return p1; 
    }
    
    //Links end node to the specified index
    public static <T> LinkedList<T> makeCycleList(T[] array, int index){
        
        LinkedList<T> ll = new LinkedList<>();
        ll.head = ll.new Node();
        LinkedList.Node temp = ll.head, iNode = null; 
       
        int i = 0;
        for(;i<array.length-1;++i){
            if(i==index)iNode = temp;
            temp.value = array[i];
            temp.next = ll.new Node(); 
            temp = temp.next;
        }
        if(index==i)iNode = temp;
        temp.value = array[i];
        temp.next = iNode;
        
        return ll;
    }
    
    public static void main(String[] args){
        Integer[] array = {1,2,3,4,5,6,7,8,9,10,11};
        LinkedList<Integer> ll = makeCycleList(array, 3);
        System.out.println(returnLoopStartNode(ll));
        System.out.println(returnLoopStartNodeM2(ll));
        
    }
}

//LinkedList

public class LinkedList <T>{
    
    Node head;
    
    public class Node{
        Node next;
        T value;
        
        Node(T value){this.value = value;}
        Node(){} 
        
        @Override 
        public boolean equals(Object o){ 
            return this.hashCode() == o.hashCode();
        }
        
        @Override
        public int hashCode(){
            return value.hashCode();
        }
        
        @Override
        public String toString(){
            return value.toString();
        }
    }
    
    public void add(T value){
        if(head==null){head = new Node(value); return;}
        Node t = head;
        while(t.next!=null){t = t.next;}
        t.next = new Node(value); 
    }
    
    public boolean isEmpty(){
        return head==null;
    }
    
    @Override
    public String toString(){
        StringBuilder bf = new StringBuilder();
        Node t = head;
        while(t!=null){
            bf.append(t.value).append(" -> ");
            t = t.next;
        }
        bf.delete(bf.length()-4, bf.length());
        return bf.toString();
    } 
}

Output:

4
4

No comments:

Post a Comment