题目重点：Oracle VO 从两链表合并追问到 K 路合并，分别用双指针和小根堆处理，明确与键值覆盖题的不同。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 各链按整数值非降序排列，可出现重复值；输出保留所有节点值，不做去重或覆盖。此点与 Oracle q1 的同 key 后链覆盖不同。
- 训练代码分配新节点，不改变原链表；同值时按来源链表索引，再按该链原顺序输出。
解题路线
- K=2 的基础解用两个指针，每步取较小节点并推进其所属链，走完后附加另一条剩余部分；若不能改原链，需复制节点。
- K 路推广：把各非空链头放小根堆，取最小节点加入输出，再把该节点的 next 放入堆。堆最多 K 项。
- 堆元素加来源编号与唯一序号作为稳定比较键，防止同值时语言运行时比较节点对象；输出所有项，因此不同链同值均保留。
- 归纳不变量：堆含各链当前最小未输出节点，堆顶为所有未输出值的最小值。每次弹出后推进该链，故结果有序且无遗漏。
手动走一遍
输入 [1,4,4]、[1,3]、[2,4]，输出 [1,1,2,3,4,4,4]。若错误套用 q1 的“后链覆盖”，会丢掉两个 1 和多个 4，本题不允许。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Merge K sorted linked lists into newly allocated nodes."""
from heapq import heappop, heappush
class ListNode:
def __init__(self, value: int, next_node: "ListNode | None" = None):
self.value = value
self.next = next_node
def merge_k_lists(heads: list[ListNode | None]) -> ListNode | None:
heap: list[tuple[int, int, int, ListNode]] = []
sequence = 0
for list_id, head in enumerate(heads):
if head is not None:
heappush(heap, (head.value, list_id, sequence, head))
sequence += 1
sentinel = ListNode(0)
tail = sentinel
while heap:
_, list_id, _, node = heappop(heap)
tail.next = ListNode(node.value)
tail = tail.next
if node.next is not None:
heappush(heap, (node.next.value, list_id, sequence, node.next))
sequence += 1
return sentinel.next
复杂度
总 N 个节点、K 条链：两链 O(N) 时间、O(N) 新输出空间；K 路堆 O(N log K) 时间、O(K) 堆空间加 O(N) 新节点。若允许原地重连，可把输出新节点空间降到 O(1)（不计堆）。
易错点与追问
容易失分的边界
- 混淆 q1 键值覆盖题，把重复值去掉。
- 堆元组仅放 (value,node)，同值时尝试比较不能排序的节点对象。
- 重连原节点时忘记保存 next，可能丢掉后缀或形成环。
继续深挖
- 分治两两合并 K 条链表能否达到 O(N log K)，与堆方案的空间和局部性有什么差异？
- 如果输入链表是网络流，如何处理最慢输入流阻塞全局顺序？
