LC23 合并 K 个升序链表

怎样从“K=3 条升序链表 [[1,4,5],[1,3,4],[2,6]]，合并为一条升序链表；先堆理解，再分治面试写法。”推导出 链表 / K 路归并 / 小根堆 / 分治 / Go，并证明每次状态变化都不会漏掉答案？

中心结论：K 路归并：堆维护各路当前头；Go 面试推荐分治 bottom-up merge，step=1/2/4 两两合并到 lists[0]。

K=3 条升序链表 [[1,4,5],[1,3,4],[2,6]]，合并为 1→1→2→3→4→4→5→6；先堆理解，再分治面试写法。

在本站主例中，K=3 条升序链表 [[1,4,5],[1,3,4],[2,6]]，合并为 1→1→2→3→4→4→5→6；先堆理解，再分治面试写法。

算法最终需要得到或观察：1→1→2→3→4→4→5→6

每轮在全部元素中重新寻找最值会重复扫描；堆持续维护下一位最值得处理的候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“优先级候车区”，明确答案需要观察什么。
2. 2状态只维护 堆（候选头）、tail（总装线尾）、各路 head 指针。
3. 3转移每一步按照 K 路归并：堆维护各路当前头；Go 面试推荐分治 bottom-up merge，step=1/2/4 两两合并到 lists[0]。
4. 4收尾读取 1→1→2→3→4→4→5→6，并复核边界与复杂度。

先确定堆顶语义，再确定超过容量时淘汰谁。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：堆（候选头）、tail（总装线尾）、各路 head 指针。

借助分治的思想，把 K 个有序链表两两合并即可。相当于是第 21 题的加强版。

K 路归并：堆维护各路当前头；Go 面试推荐分治 bottom-up merge，step=1/2/4 两两合并到 lists[0]。

执行过程中持续维护：调度塔堆、tail 总装线尾、各路 head 指针。

正确性依赖以下不变量：结果链表始终升序。；堆中只保存各轨当前暴露的头（最多 K 个）。；堆顶是下一轮要放行的全局最小候选。

面试时可以压缩为：小根堆维护 K 路头，O(N log K)/O(K)；也可分治 merge。pop 后只 push 该路 next。

落到当前题，执行机制可以压缩为：K 路归并：堆维护各路当前头；Go 面试推荐分治 bottom-up merge，step=1/2/4 两两合并到 lists[0]。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1输入 [[1,4,5],[1,3,4],[2,6]]每条链表只是一串按编号递增的矿车；还不能直接比较「整轨」谁更小。 因为：升序链表保证：每条轨道内部从左到右编号单调不减。
2. 2每轮 O(K) 扫描调度员用肉眼扫三条轨道车头，找编号最小的矿车。 因为：做法正确但慢：重复扫描浪费，需要能 O(log K) 取最小的结构。
3. 3pop 1(L0)调度塔放行最小编号矿车 1，挂到总装线末尾（复用原节点指针）。 因为：堆顶是全局最小候选；接到 tail 后结果仍升序。
4. 4pop 1(L1)调度塔放行最小编号矿车 1，挂到总装线末尾（复用原节点指针）。 因为：堆顶是全局最小候选；接到 tail 后结果仍升序。
5. 5push 6(L2)只有被弹出的那条轨道 L2 需要补入下一辆；其它路已在堆中。 因为：堆始终 = 各路当前头的集合，大小仍 ≤ K。
6. 6pop 4(L0)堆顶 4(L0) 弹出。L0 还剩 5 待入堆。 因为：堆顶始终是剩余候选中的最小编号。
7. 7pop 6(L2)，L2 耗尽堆顶 6(L2) 弹出后 L2 耗尽。堆即将变空。 因为：堆顶始终是剩余候选中的最小编号。
8. 8O(N log K) · O(K)复述三步：只看 K 个头 → 堆维护候选 → pop 后只 push 该路 next。 因为：每个节点入堆出堆各一次；堆高 O(log K)。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	length := len(lists)
	if length < 1 {
		return nil
	}
	if length == 1 {
		return lists[0]
	}
	num := length / 2
	left := mergeKLists(lists[:num])
	right := mergeKLists(lists[num:])
	return mergeTwoLists1(left, right)
}

func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists1(l1.Next, l2)
		return l1
	}
	l2.Next = mergeTwoLists1(l1, l2.Next)
	return l2
}

func main() {
    // 1. 主例
    //    输入：mode="merge-k-lists", lists=[[1,4,5],[1,3,4],[2,6]]
    //    期望：1→1→2→3→4→4→5→6
    //
    // 2. 失败 / 未命中
    //    检查：把所有节点塞进堆。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC21 合并两个有序链表；LC347 Top K
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意K=3 条升序链表 [[1,4,5],[1,3,4],[2,6]]，合并为一条升序链表；先堆理解，再分治面试写法。
2. 2重复每轮在全部元素中重新寻找最值会重复扫描；堆持续维护下一位最值得处理的候选。
3. 3优化K 路归并：堆维护各路当前头；Go 面试推荐分治 bottom-up merge，step=1/2/4 两两合并到 lists[0]。
4. 4证明结果链表始终升序。；堆中元素 = 各条轨道当前暴露的头（最多 K 个）。；堆顶 = 下一轮要放行的全局最小候选。
5. 5复杂度时间 O(N log K)，空间 O(K)