21.Merge Two Sorted Lists

合并两个排好序的单链表

• java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head,tail;
        if(l1==null&&l2==null)
            return l1;
        if(l1==null&&l2!=null)
            return l2;
        if(l1!=null&&l2==null)
            return l1;
        if(l1.val<=l2.val){
          head=new ListNode(l1.val);
          head.next=null;
          l1=l1.next;
        }else{
          head=new ListNode(l2.val);
          head.next=null;
          l2=l2.next;
        }
        tail=head;
        //同时遍历l1和l2
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
               tail.next=l1; 
                tail=tail.next;
                l1=l1.next;
                tail.next=null;
            }else{
                tail.next=l2;
                tail=tail.next;
                l2=l2.next;
                tail.next=null;
            }
            
        }
        
        //如果l1结点有多余的，按顺序加进去
        while(l1!=null){
            tail.next=l1;
            tail=tail.next;
            l1=l1.next;
            tail.next=null;
        }
        
        //如果l2结点有多余的，按顺序加进去
        while(l2!=null){
            tail.next=l2;
            tail=tail.next;
            l2=l2.next;
            tail.next=null;
        }
            
        
      return head;  
    }
}

• javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
     var head,tail;
        if(l1===null&&l2===null)
            return l1;
        if(l1===null&&l2!==null)
            return l2;
        if(l1!==null&&l2===null)
            return l1;
        if(l1.val<=l2.val){
          head=new ListNode(l1.val);
          l1=l1.next;
        }else{
          head=new ListNode(l2.val);
          l2=l2.next;
        }
        tail=head;
        //同时遍历l1和l2
        while(l1!==null&&l2!==null){
            if(l1.val<=l2.val){
               tail.next=l1; 
                tail=tail.next;
                l1=l1.next;
                tail.next=null;
            }else{
                tail.next=l2;
                tail=tail.next;
                l2=l2.next;
                tail.next=null;
            }
            
        }
        
        //如果l1结点有多余的，按顺序加进去
        while(l1!==null){
            tail.next=l1;
            tail=tail.next;
            l1=l1.next;
            tail.next=null;
        }
        
        //如果l2结点有多余的，按顺序加进去
        while(l2!==null){
            tail.next=l2;
            tail=tail.next;
            l2=l2.next;
            tail.next=null;
        }
            
        
      return head;  
    
    
};