难度: 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4运行时间: 68 ms
内存: 20.1 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
h = []
for i, head in enumerate(lists):
if head is None:
continue
heapq.heappush(h, [head.val, i, head])
while len(h) > 0:
_, i, head = heapq.heappop(h)
p.next = head
p = p.next
head = head.next
if head is not None:
heapq.heappush(h, [head.val, i, head])
return dummy.next
这个题解使用了优先队列（最小堆）来合并 K 个有序链表。首先，我们创建一个虚拟头节点 dummy，并将指针 p 指向 dummy。然后，我们遍历所有的链表头节点，将非空的头节点的值、链表编号和节点本身作为一个三元组放入最小堆中。接下来，我们不断从最小堆中取出最小值节点，将其添加到合并后的链表中，并将指针 p 向后移动。如果取出的节点还有下一个节点，我们将下一个节点的信息放入最小堆中。重复这个过程，直到最小堆为空。最后，我们返回 dummy.next，即合并后的链表的真正头节点。
时间复杂度: O((n + k) * log(k))
空间复杂度: O(k)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode() # 创建虚拟头节点
p = dummy # 指针 p 初始指向虚拟头节点
h = [] # 创建最小堆
# 遍历所有链表的头节点
for i, head in enumerate(lists):
if head is None:
continue
# 将非空头节点的值、链表编号和节点本身放入最小堆
heapq.heappush(h, [head.val, i, head])
# 不断从最小堆中取出节点，直到堆为空
while len(h) > 0:
_, i, head = heapq.heappop(h) # 取出最小值节点
p.next = head # 将节点添加到合并后的链表中
p = p.next # 指针 p 向后移动
head = head.next # 取出节点的下一个节点
if head is not None:
# 如果下一个节点不为空，将其放入最小堆
heapq.heappush(h, [head.val, i, head])
return dummy.next # 返回合并后的链表的真正头节点
最小堆（优先队列）是一种数据结构，它保证每次从中取出的元素都是具有最小值的元素。在本题解中，我使用了三元组来存储每个节点的值、其所在链表的索引和节点对象本身，并将这些三元组插入到最小堆中。最小堆会根据三元组的第一个元素（节点的值）自动维护顺序，确保每次取出的都是当前堆中值最小的节点。这样，每次取出的节点都是当前未被合并链表中值最小的节点，保持了整体的排序正确性。
直接遍历所有链表进行比较合并（如依次比较每个链表的头节点，然后选择最小的一个）会产生较高的时间复杂度，尤其是当链表数量很多时。使用最小堆可以更有效地管理和比较头节点，因为最小堆可以在对数时间内插入和删除元素，即 O(log(k))，其中 k 是链表的数量。这使得整个合并过程的时间复杂度降低到 O((n + k) * log(k))，其中 n 是所有链表中节点的总数。这种方法比直接遍历所有链表更高效，尤其是在链表数量较多或链表长度不均时。
使用虚拟头节点的主要目的是为了简化链表操作。虚拟头节点作为合并后链表的起始点，可以避免处理空链表的边界情况，并且使得链表节点的添加操作统一化，无需检查当前合并链表是否为空。这样，可以直接在虚拟头节点后开始插入节点，最后返回虚拟头节点的下一个节点作为合并后的链表的头节点。
当从最小堆中取出一个节点后，此节点已经是当前最小的节点，我将其添加到合并后的链表中。随后，如果这个节点还有下一个节点，我将这个下一个节点放入最小堆中以供后续操作。由于最小堆保证每次都会取出最小元素，且每个链表本身是有序的，这个操作不会破坏已排序的部分。这样确保了整个链表在合并时仍然保持有序。
在初始化最小堆的时候，我会检查每个链表的头节点。如果一个链表的头节点为空（即该链表为空），则我不会将其加入到最小堆中。这样，只有非空链表的头节点才会被加入到堆中，从而确保在后续的处理中不会遇到空链表带来的问题。这个策略简化了代码的复杂性，并防止了在处理过程中遇到空指针的错误。
在最坏情况下，即所有链表的节点数之和为 n，链表的个数为 k 时，时间复杂度为 O((n + k) * log(k))。这是因为每个节点和每个链表的头节点都需要经过最小堆的操作。空间复杂度为 O(k)，因为最小堆中最多同时存储 k 个节点的信息。这种算法对于节点数量和链表数量较大的情况是效率较高的，尤其是在节点分布较均匀时。