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;
    }
}