题目重点：一篇电面明确先合并两条有序链表，再追问 K 条；比较双指针与堆复杂度、并列值和原节点复用。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版各输入链表非降序、无环且彼此不共享节点；合并后可重用并重连原节点。
- 两个链表同值时先取第一条；K 条时用插入序号稳定打破堆比较的同值并列，题目没有要求来源稳定性。
- 空链表允许，K=0 返回空；若输入链表共享节点，原节点复用会产生别名问题，需要另做拷贝。
解题路线
- 两条链表用 dummy+tail 与两个游标，每次接较小头节点，同值取 a；一条耗尽后直接接上另一条剩余链。
- K 条链表把每条非空头节点放入小根堆，键为 (value,serial,node)，每弹出最小节点就接到结果尾部，再将其后继放堆。
- 弹出节点后先保存 nxt，再断开旧 next，防止结果尾部错误地带入当前来源链后续尚未比较的节点。
- 与把所有节点值展开后排序的独立参考比较 10,000 组随机输入，覆盖空、负值、重复值、K>总节点数。
手动走一遍
A=1→4→4、B=1→3→5，双指针依次取 A1、B1、B3、A4、A4、B5。若再加 C=0→4，K 路堆先弹 C0，之后按所有当前链头的值决定下一项；无需先把整条链展开。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Merge sorted linked lists, reusing the original nodes."""
import heapq
class Node:
def __init__(self, value: int, next: "Node | None" = None):
self.value = value
self.next = next
def merge_two(a: Node | None, b: Node | None) -> Node | None:
dummy = Node(0)
tail = dummy
while a is not None and b is not None:
if a.value <= b.value:
nxt = a.next
tail.next = a
a = nxt
else:
nxt = b.next
tail.next = b
b = nxt
tail = tail.next
tail.next = a if a is not None else b
return dummy.next
def merge_k(heads: list[Node | None]) -> Node | None:
heap = []
serial = 0
for head in heads:
if head is not None:
heapq.heappush(heap, (head.value, serial, head))
serial += 1
dummy = Node(0)
tail = dummy
while heap:
_, _, node = heapq.heappop(heap)
nxt = node.next
tail.next = node
tail = node
tail.next = None
if nxt is not None:
heapq.heappush(heap, (nxt.value, serial, nxt))
serial += 1
return dummy.next
复杂度
两链总 N 节点 O(N) 时间、O(1) 链接工作空间；K 链小根堆 O(N log K) 时间、O(K) 堆空间。若为了稳定输出而复制节点，额外 O(N) 空间。
易错点与追问
容易失分的边界
- K 路每步线性扫描 K 个头，退化 O(NK) 却误报 O(N log K)。
- 把 Python Node 对象放入 value 相同的堆元组而无并列键，运行时尝试比较不可排序对象。
- 复用节点时未保存 nxt 就断开 next，丢失来源链后续。
- 输入链表本身无序却直接套合并算法。
- 空链与 K=0 时访问空头。
继续深挖
- K 很大但总节点少，堆规模上界是多少？
- 若链表来自网络流，如何边拉取边合并并处理慢源？
- 若必须保留原链表不变，复制节点的成本是多少？
