Tuesday, February 2, 2016

Merge two sorted linked lists

Question: Write a method to merge two sorted linked lists

Example:
Input:
List1: 1->2->4->5->9
List2: 3->6->7->8

Output:
 1->2->3->4->5->6->7->8->9

Solution:
     /**
        * Merge two sorted linked lists
        *
        * @param l1
        * @param l2
        * @return
        */
       public static ListNode Merge(ListNode l1, ListNode l2)
       {     
              ListNode l3 = new ListNode(0);
              ListNode start=l3;
        
              while(l1!=null && l2!=null){
                 if(l1.val < l2.val) {
                     l3.next=l1;
                     l1=l1.next;
                 }
                 else {
                     l3.next = l2;
                     l2=l2.next;
                 }
                l3=l3.next;
            }
       
            l3.next = (l1==null)?l2:l1;
        
           return start.next;
       }

2 comments: