用最小堆合并多个链表

23.题目链接-来源：力扣（LeetCode）

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

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

思路：

我们的思路基于「合并2个升序链表」拓展。在 k = 2 时，我们所要获取的链表节点实际上是当前节点值最小的那个节点。于是，我们只要维护一个可以方便获取到 当前活跃链表的未处理值 的最小堆即可。这个最小堆（优先级队列）能让我们以单次平均 O(logk) 的复杂度获取所需的节点。
细节：

  • 我们需要提供一个比较器接口给最小堆，这个比较器需要返回两个节点中节点值较小的那一个节点。
  • 另外，当我们弹出一个节点，将其加入我们的返回列表以后，我们要将它的后续节点放回最小堆当中，直到后续节点为空。
  • 时刻记得我们可以用一个 dummy 节点简化链表类问题对空表的判断逻辑。
    时间复杂度：O(nlogk)
    空间复杂度：O(k)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Comparator<ListNode> cmp = (ListNode a, ListNode b) -> {
            if (a != null && b != null) {
                return a.val - b.val;
            } else if (a != null) {
                return a.val;
            } else if (b != null) {
                return b.val;
            } else {
                return 0;
            }
        };
        
        PriorityQueue<ListNode> pq = new PriorityQueue<>(cmp);
        ListNode dummy = new ListNode(), cur = dummy;
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }
        while (pq.size() > 1) {
            cur.next = pq.poll();
            cur = cur.next;
            if (cur.next != null) {
                pq.offer(cur.next);
            }
        }
        if (!pq.isEmpty()) {
            cur.next = pq.poll();
        }
        
        return dummy.next;
        
    }
}