如何合并 K 个升序链表？

直接回答：两种主流解法。1）最小堆：把 K 个链表的头节点放入堆中，每次取出最小节点接到结果尾部、并把它所在链表的下一个节点补进堆，时间 O(N log k)（N 为节点总数）、空间 O(k)。2）分治两两合并：像归并排序一样把 K 个链表配对合并，共 log k 轮，时间同样 O(N log k)，但空间 O(1)（不算递归栈）。

展开解析：复杂度推导是考点：朴素地顺序合并（第 1 个并第 2 个、结果再并第 3 个……）是 O(Nk)，因为前面合并出的大链表被反复扫描；两两合并让每条链表只参与 log k 次合并，总工作量 N·log k。堆版本适合「K 很大但每个链表是流式到达」的场景（迭代器惰性取值），分治版本更省内存且缓存友好。实现细节：堆中元素要附带链表编号避免节点值相等时比较 Node 对象报错（Python 里 (val, idx, node) 三元组）；分治版用迭代而非递归可避免 log k 的栈深讨论。追问方向：与「合并 K 个有序数组」的异同、外部排序归并阶段的联系（K 路归并 + 败者树）。

示例：

import heapq

def merge_k_lists(lists):
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = tail = type(lists[0])(0) if lists else None
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next, tail = node, node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next if dummy else None