Monday, September 2, 2013

Merge Two Sorted Link Lists into a Third Sorted List

Merge two Sorted Linked List into a Third Linked List


Java program to Merge two sorted lists into a third list. Below program has, both a recursive and iterative version methods


public class MergeLinkList {

    private Link mergeRecursive( Link l1, Link l2 ) {
        if ( l1 == null) return l2;
        if ( l2 == null ) return l1;
       
        Link mergedhead = null;
       
        if ( l1.value() < l2.value() ) {
            mergedhead = l1;
            mergedhead.next = mergeRecursive(l1.next, l2);
        }else {
            mergedhead = l2;
            mergedhead.next = mergeRecursive(l1, l2.next);
        }
        return mergedhead;
    }
   
    private Link mergeInterative( Link  l1, Link l2 ) {
        if ( l1 == null) return l1;
        if ( l2 == null ) return l2;
       
        Link p1 = l1;
        Link p2 = l2;
       
        Link mergedHead= null;
        Link last = mergedHead;
       
        while ( p1!= null && p2 != null ) {
        if ( p1.value() < p2.value() ) {
          if ( last == null ) {
              last = new Link(p1.value());
              mergedHead = last;
          }else {
              last.next = new Link( p1.value());
              last = last.next;
          }
         p1 = p1.next;
        }else {
             if ( last == null ) {
                  last = new Link(p2.value());
                  mergedHead = last;
              }else {
                  last.next = new Link( p2.value());
                  last = last.next;
              }
             p2 = p2.next;
        }               
        }
        if ( p1 != null ) {
            insertAll( p1, last );
        }else
            insertAll( p2, last );
       
        return mergedHead;
    }
   
    private void insertAll( Link p1, Link last ) {
        do {
            last.next = new Link(p1.value());
            p1 = p1.next;
        }while ( p1 != null );
    }
   
public static void main( String[] args ) {
       
        /*
          * .................n..........n.............n.........n.............n.......................n............n..........        ---> Number line for Array1, has 8 numbers in ascend
         * .....n...n...........n......... n...n..........n.........n.................................................................... 
             * */
       
            int[] ar1 = new int[] { 45, 56, 77, 89, 150, 187, 198};
            int len1 = 7;
           
            int[] ar2 = new int[] { 23, 29, 47, 59, 67, 80, 106 };
            int len2 = 7;
           
            Link l1 = Link.build( ar1 );
            Link l2 = Link.build(ar2);
           
            MergeLinkList merge = new MergeLinkList();
            Link mergedIter = merge.mergeInterative(l1, l2);
            mergedIter.print(mergedIter);
           
            System.out.println("Prining recursively");
           
            Link mergedRecursive = merge.mergeRecursive(l1, l2);
            mergedRecursive.print(mergedRecursive);
           
           
    }
}

No comments:

Post a Comment