LeetCode【0023】合并K个生序链表

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

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

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

提示：

• $0\le lists.length\le 10^4$
• $0\le lists[i].length\le 500$
• $-10^4\le lists[i][j]\le 10^4$
• $lists[i]$ 按 升序 排列
• $lists[i].length$ 的总和不超过 $10^4$

---

2 求解方法：最小堆（优先队列）

2.1 方法思路

方法核心

• 使用最小堆（优先队列）来维护当前所有链表头节点中的最小值
• 通过包装类使ListNode可比较
• 每次从堆中取出最小值，并将其下一个节点加入堆中

实现步骤

• 初始化阶段：
  a. 创建虚拟头节点和当前指针
  b. 创建空的优先队列
  c. 将所有链表的头节点加入优先队列
• 合并过程：
  a. 循环从优先队列中取出最小节点
  b. 将最小节点连接到结果链表
  c. 如果被取出节点有后继节点，将后继节点加入优先队列
• 返回结果：
  a. 返回虚拟头节点的下一个节点

方法示例

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

步骤演示：

1. 初始状态：
heap = [1(A), 1(B), 2(C)]  # A,B,C代表不同链表
result = dummy -> NULL

2. 第一次取最小值(1来自A)：
heap = [1(B), 2(C), 4(A)]
result = dummy -> 1 -> NULL

3. 第二次取最小值(1来自B)：
heap = [2(C), 3(B), 4(A)]
result = dummy -> 1 -> 1 -> NULL

4. 第三次取最小值(2来自C)：
heap = [3(B), 4(A), 6(C)]
result = dummy -> 1 -> 1 -> 2 -> NULL

5. 依此类推，最终结果：
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

2.2 Python代码

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 导入优先队列
        from heapq import heappush, heappop
        
        # 定义一个包装类来使ListNode可比较
        class ListNodeWrapper:
            def __init__(self, node):
                self.node = node
            
            def __lt__(self, other):
                return self.node.val < other.node.val
        
        # 创建虚拟头节点
        dummy = ListNode(0)
        current = dummy
        # 创建优先队列
        heap = []
        
        # 将所有链表的头节点加入优先队列
        for i, head in enumerate(lists):
            if head:
                # 将节点包装后压入堆中
                heappush(heap, ListNodeWrapper(head))
        
        # 当优先队列非空时循环
        while heap:
            # 取出最小值节点
            wrapper = heappop(heap)
            node = wrapper.node
            # 连接到结果链表
            current.next = node
            current = current.next
            
            # 如果取出节点的下一个节点存在，将其加入优先队列
            if node.next:
                heappush(heap, ListNodeWrapper(node.next))
        
        return dummy.next

2.3 复杂度分析

• 时间复杂度：$O(Nlogk)$，N 是所有节点的总数，k 是链表的条数
  • 每个节点都要经过一次入堆出堆操作
  • 堆操作的时间复杂度是 log k
• 空间复杂度：$O(k)$
  • 优先队列中最多同时存在 k 个节点
  • 不计算输出结果占用的空间

---

3 题目总结

题目难度：困难
数据结构：链表、最小堆（优先队列）

原文地址：https://blog.csdn.net/qq_32882309/article/details/143732957

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！