【LeetCode 热题100】23：归并 K 个升序链表（详细解析）（Go语言版） ...

LeetCode 热题 23：归并 K 个升序链表（详细解析）

标题描述

   LeetCode 23. Merge k Sorted Lists
  给你一个链表数组，每个链表都已经按升序分列。
请你将所有链表归并到一个升序链表中，返回归并后的链表。
  <hr> 示例 1：

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

复制代码

示例 2：

1. 输入：lists = []
2. 输出：[]

复制代码

示例 3：

1. 输入：lists = [[]]
2. 输出：[]

复制代码

<hr> 解题思绪一：优先队列（最小堆）

利用最小堆（Priority Queue）维护 k 个链表的头节点，每次取堆顶最小值节点，接入结果链表。
✅ 步调解析

• 初始化最小堆，将每个非空链表的头节点入堆。
  
• 不停从堆中弹出最小值节点，将其参加结果链表。
  
• 如果弹出的节点有 next 节点，则将 next 节点入堆。
  
• 最后返回结果链表头部。
  

<hr> Go 实现（利用 heap 接口）

1. type ListNode struct {
2.    
3.     Val  int
4.     Next *ListNode
5. }
7. type NodeHeap []*ListNode
9. func (h NodeHeap) Len() int           {
10.     return len(h) }
11. func (h NodeHeap) Less(i, j int) bool {
12.     return h[i].Val < h[j].Val }
13. func (h NodeHeap) Swap(i, j int)      {
14.     h[i], h[j] = h[j], h[i] }
16. func (h *NodeHeap) Push(x interface{
17.    

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。