🚀 LeetCode 热题 23：合并 K 个升序链表（详细解析）
📌 题目描述
LeetCode 23. Merge k Sorted Lists
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
🎯 示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
🎯 示例 2：
输入：lists = []
输出：[]
🎯 示例 3：
输入：lists = [[]]
输出：[]
💡 解题思路一：优先队列（最小堆）
使用最小堆（Priority Queue）维护 k 个链表的头节点，每次取堆顶最小值节点，接入结果链表。
✅ 步骤解析
- 初始化最小堆，将每个非空链表的头节点入堆。
- 不断从堆中弹出最小值节点，将其加入结果链表。
- 如果弹出的节点有 next 节点，则将 next 节点入堆。
- 最后返回结果链表头部。
💻 Go 实现（使用 heap 接口）
type ListNode struct {
Val int
Next *ListNode
}
type NodeHeap []*ListNode
func (h NodeHeap) Len() int {
return len(h) }
func (h NodeHeap) Less(i, j int) bool {
return h[i].Val < h[j].Val }
func (h NodeHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x interface{
}) {
*h = append(*h, x.(*ListNode))
}
func (h *NodeHeap) Pop() interface{
} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func mergeKLists(lists []*ListNode) *ListNode {
h := &NodeHeap{
}
heap.Init(h)
for _, node := range lists {
if node != nil {
heap.Push(h, node)
}
}
dummy := &ListNode{
}
curr := dummy
for h.Len() > 0 {
node := heap.Pop(h).(*ListNode)
curr.Next = node
curr = curr.Next
if node.Next != nil {
heap.Push(h, node.Next)
}
}
return dummy.Next
}
💡 解题思路二：分治合并（归并）
- 将 k 个链表两两合并，逐步缩小范围。
- 类似归并排序的思想。
✅ 步骤解析
- 每次将链表对半拆分，递归合并每一对链表。
- 使用合并两个有序链表的经典方法。
💻 Go 实现
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
return mergeRange(lists, 0, len(lists)-1)
}
func mergeRange(lists []*ListNode, l, r int) *ListNode {
if l == r {
return lists[l]
}
mid := (l + r) / 2
left := mergeRange(lists, l, mid)
right := mergeRange(lists, mid+1, r)
return mergeTwoLists(left, right)
}
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{
}
curr := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
curr.Next = l1
l1 = l1.Next
} else {
curr.Next = l2
l2 = l2.Next
}
curr = curr.Next
}
if l1 != nil {
curr.Next = l1
} else {
curr.Next = l2
}
return dummy.Next
}
📊 解法对比 & 复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 特点说明 |
|---|---|---|---|
| ✅ 最小堆 | $O(n \log k)$ | $O(k)$ | 快速选择当前最小节点 |
| ✅ 分治合并 | $O(n \log k)$ | $O(\log k)$ | 简洁高效，适合面试常考套路 |
- 其中，$n$ 是所有链表节点总数，$k$ 是链表数量。
🧠 总结
- 🔧 如果要求效率，最小堆优先，适合在线合并场景。
- 📚 如果偏向代码整洁，可选择分治合并，便于拓展与理解。
- 💡 重点掌握：链表合并逻辑 + 堆操作 + 分治模板。
✅ 如果你觉得这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、关注 💻，我会持续更新更多高质量 LeetCode 热题详解！🚀📌🎯
