Sunday, March 8, 2015

21. Merge Two Sorted Lists Leetcode Java

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Solution:
Pick one of them as the target list, and merge the other one into it. I use a preDummy node to avoid processing the head corner case. Compare node each by each and insert the l2 if needed. 
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
    if(l1==null) return l2;  
    if(l2==null) return l1;  
    ListNode preDummy=new ListNode(0);  
    preDummy.next=l1;  
    ListNode pre=preDummy;  
    while(pre.next!=null){  
      if(l2==null) return preDummy.next;  
      if(pre.next.val<l2.val) pre=pre.next;  
      else {  
        ListNode temp=l2.next;  
        l2.next=pre.next;  
        pre.next=l2;  
        l2=temp;  
      }  
    }  
    pre.next=l2;  
    return preDummy.next;  
   }  

No comments:

Post a Comment