跳转至

23. 合并 K 个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1:

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]

示例 2:

输入：lists = []

输出：[]

复杂度

分治思想：先合并前一半，在合并后一半，最后合并两个链表。

  • 时间复杂度：\(O(n \ logk)\)，其中 \(k\) 为 lists 的长度，\(n\) 为所有链表的节点数之和。
    • 每个节点参与链表合并的次数为 \(O(log\ ⁡k)\) 次，一共有 \(n\) 个节点，所以总的时间复杂度为 \(O(n \ log\ ⁡k)\)。
  • 空间复杂度：\(O(log\ k)\)。
    • 递归深度为 \(O(log\ ⁡k)\)，需要用到 \(O(log\ ⁡k)\) 的栈空间。Python 忽略切片产生的额外空间。

题解

Go
func mergeTwoLists(list1, list2 *ListNode) *ListNode {
    dummy := &ListNode{} // 用哨兵节点简化代码逻辑
    cur := dummy         // cur 指向新链表的末尾
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            cur.Next = list1 // 把 list1 加到新链表中
            list1 = list1.Next
        } else { // 注：相等的情况加哪个节点都是可以的
            cur.Next = list2 // 把 list2 加到新链表中
            list2 = list2.Next
        }
        cur = cur.Next
    }
    // 拼接剩余链表
    if list1 != nil {
        cur.Next = list1
    } else {
        cur.Next = list2
    }
    return dummy.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    m := len(lists)
    if m == 0 { // 注意输入的 lists 可能是空的
        return nil
    }
    if m == 1 { // 无需合并，直接返回
        return lists[0]
    }
    left := mergeKLists(lists[:m/2]) // 合并左半部分
    right := mergeKLists(lists[m/2:]) // 合并右半部分
    return mergeTwoLists(left, right) // 最后把左半和右半合并
}
Python
class Solution:
    # 21. 合并两个有序链表
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 把 list1 加到新链表中
                list1 = list1.next
            else:  # 注：相等的情况加哪个节点都是可以的
                cur.next = list2  # 把 list2 加到新链表中
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2  # 拼接剩余链表
        return dummy.next

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        m = len(lists)
        if m == 0: return None  # 注意输入的 lists 可能是空的
        if m == 1: return lists[0]  # 无需合并，直接返回
        left = self.mergeKLists(lists[:m // 2])  # 合并左半部分
        right = self.mergeKLists(lists[m // 2:])  # 合并右半部分
        return self.mergeTwoLists(left, right)  # 最后把左半和右半合并

参考