Monday 23 September 2013

Find the merging point in given 2 linked lists

Example:
Input :







Output : 4

Algorithm
     1) Find lengths of both lists
     2) take the difference d of the lengths
     3) make d steps in longer list
     4) step in both lists in parallel until links to next node match

Implementation

class FindTheMergingPoingInGiven2LinkedList{
    static class LinkedList{
        int data;
        LinkedList next = null;
     
        public LinkedList(int data){
            this.data = data;
        }
     
        public void insertAtEnd(int data){
            LinkedList head = this;
            LinkedList newNode = new LinkedList(data);
         
            if(head == null){
                head = newNode;
                return;
            }
         
            while(head.next != null){
                head = head.next;
            }
            head.next = newNode;
        }
     
        public void print(LinkedList head){
            while(head != null){
                System.out.print(head.data + " ");
                head = head.next;
            }
            System.out.println();
        }
     
        //time : O(N)
        public static int length(LinkedList head){
            int length = 0;
            while(head != null){
                length++;
                head = head.next;
            }
            return length;
        }
                   
        public static LinkedList findMergingPoint(LinkedList head, LinkedList head2){
            //Base condition
            if(head == null && head2 == null)
                return null;
            
            int length = length(head);  //length of first list
            int length2 = length(head2);  //length of second list
            
            int diff;  //difference d of the lengths
            LinkedList bigList, smallList;
            if(length > length2){
                diff = length - length2;
                bigList = head;
                smallList = head2;
            }else{
                diff = length2 - length;
                bigList = head2;
                smallList = head;
            }
            
             //make d steps in longer list
            for(int i = 0; i < diff; i++)
                bigList = bigList.next;
            
            //make step in both lists in parallel until links to next node match      
           //or null     
            while(bigList != null && smallList != null){
                if(bigList == smallList) 
                    return bigList; 
                
                bigList = bigList.next;
                smallList = smallList.next;
            }
            return null;
        }
    }
 
    public static void main(String []args){
        LinkedList head = new LinkedList(1);
        head.insertAtEnd(2);
        head.insertAtEnd(3);
        head.insertAtEnd(4);
        head.insertAtEnd(5);
        head.insertAtEnd(6);
     
        LinkedList head2 = new LinkedList(7);
        head2.insertAtEnd(8);
        head2.next.next = head.next.next.next;     //merging the lists
     
     
        head2.print(head);
        head2.print(head2);
     
        LinkedList mergePoint = LinkedList.findMergingPoint(head, head2);
        System.out.println(mergePoint.data);
    }

}

Time Complexity: O(max(m, n))
Space Complexity : O(1)

No comments:

Post a Comment