题目重点：每路只保留一个候选，使用值和来源编号比较，解释惰性输出、缓冲与输入有序性边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练每路升序且可单次迭代，值可比较；保留重复值，空链表允许。
- 展示Python生成器，链表可用逐node.value前进的迭代器适配，不预先转成数组。
- 相同值按来源编号稳定输出；只要求值序列正确时该平局规则不是必要题意。
- 发现某路降序时报错，但此前输出无法撤回；若必须全量校验后原子输出，需要先验证或缓冲，失去完全流式特性。
解题路线
- 每条有序链表未消费部分的最小值就是其当前头节点；全局最小值一定是某一路的当前头。因此堆只放每路一个候选，不把所有N个节点都入堆。
- heap条目为(value,source_id,iterator)。value是主键，source_id是固定唯一来源编号，避免相同值时Python尝试比较不可排序的Node或iterator对象。任意时刻同一路至多一个条目，第三字段不会被用作平局比较。
- 初始化取各路首元素并heapify，之后弹出最小条目输出，且只从该来源补下一个。这个替换保持每路头候选覆盖不变量，其余来源不需要前进。
- 正确性归纳：堆中最小头不大于任何未输出元素，输出它是下一个全局值；补入该路后继仍保持所有路头完整。全部堆空意味着每路已耗尽，输出既不漏也不重复。
- 用yield让调用方消费输出，避免累计完整结果。每路只持有一个头、迭代器及底层必要缓冲；如果底层是已经全部加载在内存的链表，本算法不会自动释放调用方持有的整条链，也不能声称总进程内存只有O(k)。
- 如果必须返回合并链表且允许改输入，可连接弹出的原node并推进保存的next，避免重新分配N节点；若输入只读则新建N个输出节点。两种方式都需说明节点所有权与尾指针清理。
- 外部存储时为每路加有界块缓冲，控制打开文件数量、IO预取和背压；k超过可用文件句柄时做分批多路归并，轮数增加。一个请求取消消费后要关闭资源，不能让迭代器一直占连接。
- 独立验证用短数组flatten后全排序检查值和重复数，并用一次性计数生成器确认请求少量输出只推进有限输入。不能为了测试方便把实际大输入全部转换成list。
手动走一遍
三路[1,4]、[1,3]、[]的堆先有(1,0)和(1,1)，按来源0输出第一个1并补4，再输出来源1的1并补3，结果1,1,3,4。两个Node值同为1不会去比较Node对象。消费者只取第一个值时，初始化之外不读取全部链表。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
import heapq
def merge_sorted_streams(streams):
heap = []
for source, stream in enumerate(streams):
iterator = iter(stream)
try:
value = next(iterator)
except StopIteration:
continue
heap.append((value, source, iterator))
heapq.heapify(heap)
while heap:
value, source, iterator = heapq.heappop(heap)
yield value
try:
following = next(iterator)
except StopIteration:
continue
if following < value:
raise ValueError('input stream is not sorted')
heapq.heappush(heap, (following, source, iterator))
复杂度
设k路、N总元素，初始化扫描O(k)、heapify O(k)，输出O(N log(k+1))；堆和迭代器O(k)额外空间，不含输入、输出及底层缓冲。消费成list另需O(N)输出空间；外部归并IO成本按块与轮数另计。
易错点与追问
容易失分的边界
- heap只存(value,node)，同值时比较node报错。
- 把全部节点入堆导致O(N)辅助内存。
- 生成器外又立即list化却声称输出无需存储。
- 把已有链表占用与新增堆内存混为一谈。
继续深挖
- 返回节点且允许改链时怎样连接？
- 每路大小不同，分治与heap有什么取舍？
- k超过句柄限制怎样分批？
- 某路无限且所有值更小，其他路是否可能一直等待？
