21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

本题关键之处（完整代码见文末）：

  • 使用哨兵节点降低复杂度
  • 基本的链表操作

  • image.png

    1. //简化代码
    2. //迭代法 哨兵模式,复杂度On+m,O1
    3. func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    4.   dummy := &ListNode{}
    5.   prev := dummy
    7.   for l1 != nil && l2 != nil {
    8.       if l1.Val <= l2.Val {
    9.           prev.Next = l1
    10.           l1 = l1.Next
    11.       } else {
    12.           prev.Next = l2
    13.           l2 = l2.Next
    14.       }
    15.       prev = prev.Next
    16.   }
    18.   if l1 == nil {
    19.       prev.Next = l2
    20.   }
    21.   if l2 == nil {
    22.       prev.Next = l1
    23.   }
    25.   return dummy.Next
    26. }
    //迭代法，哨兵模式,复杂度On+m,O1
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  prehead := &ListNode{}    //定义一个头指针，不停的往前走
  result := prehead        //保存头指针，日后从头的初始状态推完整链表！

  for l1 != nil && l2 != nil {
      if l1.Val < l2.Val {    //链表头相比较，小的在前
          prehead.Next = l1    //新链表头尾小的那个
          l1 = l1.Next        //前进
      }else {
          prehead.Next = l2
          l2 = l2.Next
      }
      prehead = prehead.Next 
  }

  if l1 != nil {        //若l1还有空余=l2先空了，把l1直接加在后面就行
      prehead.Next = l1
  }
  if l2 != nil {
      prehead.Next =l2
  }
  return result.Next    //返回的是初始指针result
}

解题思路

  1. 先判断某个链表是否为空，如果为空直接返回另一个链表
  2. 如果两个链表均不为空，根据两链表的表头大小决定下一层的递归参数。因为 mergeTwoLists(list1, list2)函数会返回 list1 和 list2 两个链表合并后的结果，所以如果 l1.val < l2.val, 把 l1.next 和 l2 两个链表的合并后的结果赋值给 l1.next, 这样就完成了2个链表的合并，l1.val > l2.val同理。
//递归，通法，复杂度On+m,On
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    var res *ListNode     //定义一个结果节点
    if l1.Val <= l2.Val {    //比较头节点大小，指向小节点头
        res = l1
        res.Next = mergeTwoLists(l1.Next, l2)    //小节点前进，继续比较
    } else {
        res = l2 
        res.Next = mergeTwoLists(l2.Next, l1)
    }

    return res
}