【LeetCode 算法】Merge k Sorted Lists 合并 K 个升序链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode 算法】Merge k Sorted Lists 合并 K 个升序链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Merge k Sorted Lists 合并 K 个升序链表

问题描述：

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

$k == lists.length\\ 0 <= k <= 10^4\\ 0 <= lists[i].length <= 500\\ -10^4 <= lists[i][j] <= 10^4\\ lists[i] 按升序排列\\ lists[i].length 的总和不超过 10^4$

分析

要求非常简单，就是把多个有序链表合并成为一个有序链表。

这里有k个链表，以之前的经验，可以相邻的2个合并，假设链表的平均长度都是L，那么按照这个方式处理，需要合并k-1次，第一次的平均时间复杂度为 $O (2 L)$ ,第二次的时间复杂度为 $O (3 L)$ ,所以第k-1次的时间复杂度就是 $O ((k - 1) L)$ .
所以在这个思路下的时间复杂度就是 $O((k^2)N)$ ,但是好处是空间是 $O (1)$ .

思路没有大问题，但是数据规模大的情况下，这个时间复杂度并不友好。

为什么这个思路下的时间复杂度会达到K^2,你细品。

既然每个链表都是有序的，那么可以从k个节点中找到最小的加入最终结果的尾部。
如果是朴素的找法，从k个节点找最小的，单次耗时 $O (k),$ 一共有kL个节点，时间复杂度也是 $O((K^2)N)$ 。

如果利用有序的特殊条件，可以找到对数时间复杂度的方法，比如分治归并，或者是小顶堆。
在不同的角度上降低了时间复杂度。

分治归并与原本的归并比较起来，它只需要合并 $l o g K$ 次。
小顶堆的思路，则是可以在 $l o g K$ 的时间复杂度下，找到最小的节点。

目前没有比这2个思路更快的，时间复杂度都是 $O (N K l o g K),$ 但是空间复杂度一个是 $O (l o g K)$ ,一个是 $O (K)$ .

代码

Heap

public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>((a,b)->{return a.val-b.val;});
        ListNode h = new ListNode(0);
        for(ListNode no: lists){
            if(no==null) continue;
            pq.offer(no);
        }
        ListNode p = h;
        while(!pq.isEmpty()){
            ListNode cur = pq.poll();
            ListNode nx = cur.next;
            
            p.next = cur;
            p = cur;

            if(nx!=null) pq.offer(nx); 
        }
        return h.next;
    }