合并K个有序链表的时空复杂度分析：我的堆实现推导正确吗

一、现有实现复杂度结论修正 #

你定义的n为链表集合的大小，m为所有链表中最长的单链表长度，最坏情况下所有链表长度都等于m，总元素数为n*m，基于这个前提给出修正后的复杂度结论：

• 空间复杂度：你的判断正确，最坏为O(n*m)。你将所有元素全部存入最小堆，同时新建了等长的结果链表，两者的空间开销都是和总元素数成正比的。
• 时间复杂度：你的原有判断有误，正确的最坏时间复杂度是O(n*m*log(n*m))。原因是最小堆的插入、弹出操作的时间复杂度和堆的大小成对数关系，你实现里堆的大小最坏为n*m，所有元素各执行一次插入、一次弹出，总操作次数为2*n*m，每次操作开销为O(log(n*m))，因此整体时间复杂度为O(n*m*log(n*m))。

二、现有实现的可优化点 #

你的实现没有用到「每个输入链表本身已经有序」的特性，等价于把所有元素收集起来全排序后重建链表，存在明显的优化空间。

三、优化方案及对应复杂度 #

优化思路是仅把每个链表的当前待比较头节点存入堆，而不是所有元素：

1. 初始阶段仅把所有非空链表的头节点放入最小堆，堆的最大大小为n
2. 每次弹出堆顶的最小节点，拼接到结果链表后，若该节点存在后继节点，就把后继节点放入堆中
   该方案的复杂度为：

• 空间复杂度：最坏O(n)，仅堆的存储开销，若允许复用原链表节点不需要额外新建节点，空间开销会远低于原有实现
• 时间复杂度：最坏O(n*m*logn)，每个元素仍各执行一次入堆、出堆，但堆的最大大小为n，每次堆操作的开销降为O(logn)，在n远小于m的场景下性能提升非常明显

四、优化实现代码示例 #

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> a) {
        // 最小堆存储ListNode，按节点值排序
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        // 初始仅入堆所有非空链表的头节点
        for (ListNode head : a) {
            if (head != null) {
                minHeap.add(head);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll();
            curr.next = minNode;
            curr = curr.next;
            // 后继节点存在则入堆
            if (minNode.next != null) {
                minHeap.add(minNode.next);
            }
        }
        return dummy.next;
    }
}

内容的提问来源于stack exchange，提问作者Lovesh Dongre