1. 先处理头结点

1.1 分析

• 把两个链表中较小的头作为新链表的头
• 依次比较两个链表未合并部分的头，较小者插入新表的尾
• 处理未走到尽头的链表

  1.2 代码

  public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        //先处理头
        ListNode head = (l1.val <= l2.val)? l1:l2;
        ListNode tail = head;
        l1 = (head == l1)? l1.next:l1;
        l2 = (head == l2)? l2.next:l2;
        while(l1 != null && l2 != null)
        {
            if(l1.val <= l2.val){
                tail.next = l1;
                l1 = l1.next;
            }else{
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 == null)? l2 : l1;
        return head;
    }
  }

  1.3 复杂度

  空间：O(1)
  时间：O(2)

2. 辅助头结点

2.1 分析

先建立辅助头结点，省去了单独处理头的麻烦，最后直接返回辅助头的next

2.2 代码

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        //辅助头
        ListNode head = new ListNode(0);
        ListNode tail = head;
        //以下同上一方法
        while(l1 != null && l2 != null)
        {
            if(l1.val <= l2.val){
                tail.next = l1;
                l1 = l1.next;
            }else{
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 == null)? l2 : l1;
        return head.next;
    }
}