题目重点：依据 OCI Consultant Engineer 电面的完整示例，使用小根堆合并 K 条 key 排序链表，同 key 由较后输入链表覆盖。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每条输入链表的 key 严格递增，同一 key 在不同链表可出现；较大输入链表索引代表“后面出现的链表”。
- 返回新的 (key,value) 列表，不修改输入；空链表允许，所有 key 都可比较。题目没有规定同一链内重复 key 的覆盖规则，训练实现明确拒绝。
解题路线
- 把每条非空链表的头节点以 (key, listIndex, position) 压入小根堆。堆顶总是尚未处理的最小 key。
- 取当前最小 key，并连续弹出所有同 key 项；只保留来源链表编号最大的 value。弹出某链表项时把该链下一项压堆，因此同 key 必须一直处理到堆顶变化。
- 处理完一个 key 才向结果写一项，保证覆盖规则与升序同时成立。归纳不变量：堆中至多每条链一个待处理头，已输出 key 小于所有堆中 key。
- 如果只为小规模练习，也可扫描所有项用字典覆写再排序，时间 O(N log U)、空间 O(U)；堆能利用已有链内有序性并在线输出。
手动走一遍
题目 l0=[(1,70),(3,20),(5,30)]、l1=[(2,40),(3,50)]、l2=[(1,15),(4,80),(5,90)]。key=1 时 l2 覆盖 l0 得 15；key=3 时 l1 覆盖 l0 得 50；key=5 时 l2 覆盖 l0 得 90，最终 [(1,15),(2,40),(3,50),(4,80),(5,90)]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Merge sorted key/value sequences, with later input lists overriding earlier."""
from heapq import heappop, heappush
def merge_key_value_lists(lists: list[list[tuple[int, int]]]) -> list[tuple[int, int]]:
heap: list[tuple[int, int, int]] = []
for list_id, items in enumerate(lists):
if items:
heappush(heap, (items[0][0], list_id, 0))
result: list[tuple[int, int]] = []
while heap:
key = heap[0][0]
chosen_list = -1
chosen_value = 0
while heap and heap[0][0] == key:
_, list_id, position = heappop(heap)
item_key, value = lists[list_id][position]
assert item_key == key
if list_id > chosen_list:
chosen_list = list_id
chosen_value = value
next_position = position + 1
if next_position < len(lists[list_id]):
next_key = lists[list_id][next_position][0]
if next_key <= key:
raise ValueError("Each input list must have strictly increasing keys")
heappush(heap, (next_key, list_id, next_position))
result.append((key, chosen_value))
return result
复杂度
总 N 个条目、K 条链，堆最多 K 个元素，时间 O(N log K)，额外堆空间 O(K)，输出 O(U)（U 为不同 key 数）。空输入返回空列表；K=1 时仍正确。
易错点与追问
容易失分的边界
- 只取堆弹出的第一个同 key 值，遗漏其他链表的覆写。
- 用值大小或堆弹出顺序决定覆盖，实际应按输入链表顺序。
- 在处理 key 过程中忘记推进链表头，导致同 key 的后继节点漏计。
- 把小根堆误认为按 value 排序；排序键是 key。
继续深挖
- 若每条链内部允许同 key 重复，需明确“同一链后项”是否覆盖，并调整候选比较规则。
- 若输入是不可回放流，如何边读边输出且控制 K 个读取器的背压？
- 若只有 U 个不同 key 而 N 远大于 U，字典覆写再排序与堆方案的内存取舍是什么？
