合并 K 个升序链表

难度: Hard

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

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

注意：本题与主站 23 题相同： https://leetcode-cn.com/problems/merge-k-sorted-lists/

Submission

运行时间: 52 ms

内存: 18.6 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def merge(head1, head2):
            dummy = ListNode()
            p = dummy
            while head1 and head2:
                if head1.val > head2.val:
                    p.next = head2
                    head2 = head2.next
                else:
                    p.next = head1
                    head1 = head1.next
                p = p.next
            if head1:
                p.next = head1
            if head2:
                p.next = head2
            return dummy.next
        
        def merge_list(l, r):
            if l == r:
                return lists[l]
            if l > r:
                return
            mid = l + (r-l)//2
            # 这里必须上面是mid，下面mid+1，否则merge_list(mid+1, r)可能无限递归：(l, m, r) = (1, 1, 2)
            head1 = merge_list(l, mid)
            head2 = merge_list(mid+1, r)  
            return merge(head1, head2)
        return merge_list(0, len(lists)-1)

Explain

这个题解采用了分治法的思想，将合并 k 个链表的问题分解为合并两个链表的问题。具体做法是： 1. 如果链表数组长度为 1，直接返回该链表。 2. 如果链表数组长度大于 1，将其分为两半，分别对这两半递归地进行合并。 3. 合并两个链表的过程中，使用一个虚拟头节点，依次比较两个链表的节点值，将较小的节点接到结果链表上，直到其中一个链表为空，再将另一个链表剩余部分接到结果链表上。

时间复杂度: O(kn * log(k))

空间复杂度: O(log(k))

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def merge(head1, head2):
            dummy = ListNode()
            p = dummy
            while head1 and head2:
                if head1.val > head2.val:
                    p.next = head2
                    head2 = head2.next
                else:
                    p.next = head1
                    head1 = head1.next
                p = p.next
            if head1:
                p.next = head1
            if head2:
                p.next = head2
            return dummy.next
        
        def merge_list(l, r):
            if l == r:
                return lists[l]
            if l > r:
                return
            mid = l + (r-l)//2
            head1 = merge_list(l, mid)
            head2 = merge_list(mid+1, r)
            return merge(head1, head2)
        return merge_list(0, len(lists)-1)

Explore

在合并 k 个链表时，递归方法能够将问题自然地分解为更小的子问题，这与分治法的核心思想相吻合。使用递归，代码更为简洁且易于理解。相较于迭代，递归可能在内存使用上稍高，因为每次递归调用都会占用一定的调用栈空间。在极端情况下，如递归深度过大，可能导致栈溢出。性能方面，递归与迭代相比通常有更多的函数调用开销，但在合并链表这个问题上，递归的时间复杂度与迭代相当，都可以达到 O(Nlogk)，其中 N 是所有链表中节点总数，k 是链表数目。

当前的解决方案没有特别处理`lists = []`或`lists = [[]]`的情况。对于`lists = []`，函数会在`merge_list(0, -1)`时返回`None`，这是正确的。但是，为了让代码更加健壮和直观，可以在`mergeKLists`函数的开始添加检查条件：`if not lists: return None`。这样可以明确表示当输入为空时，输出也应该为空。此外，对于`lists`中每个元素都是空链表的情况，我们可以在递归函数`merge_list`中进行处理，确保返回一个空链表而非`None`。

在`merge_list`函数中，当`l > r`时返回`None`是处理边界情况的一种方式，确保不会有非法的数组访问。这通常不会影响最终结果，因为这种情况发生在递归分解到不存在的子区间时。在实际合并过程中，如果某一部分的递归返回`None`（表示这部分没有链表存在），合并函数`merge`能够处理一个或两个链表为`None`的情况。确保即使是空链表也能正确合并，不会对最终结果产生负面影响。