LeetCode 23 合并K个升序链表

LeetCode 23 合并K个升序链表

---

题目:

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]


提示：

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

题解:

此题我们使用小顶堆数据结构巧解此事:

解题步骤如下:
1.创建K个指针依次指向K个链表的表头
2.定义小顶堆，比较对象是K指针指向的节点的值
3.将K个指针放入小顶堆
4.定义哨兵节点Head
5.取小顶堆顶部节点H，此节点为当前堆中最小值，将此节点链接到哨兵节点之后，
  然后将此指针后移(如果有),然后重新放入小顶堆中重拍
6.重复步骤5直至堆中节点全部推出

代码：

private ListNode process(ListNode[] lists){
    ListNode head = new ListNode(0);
    ListNode p = head;
    if (lists.length == 0) return null;
    PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(lists.length, Comparator.comparingInt(o -> o.val));
    for (ListNode node : lists) {
        if (node != null) {
            priorityQueue.offer(node);
        }
    }
    while (!priorityQueue.isEmpty()) {
        ListNode node = priorityQueue.poll();
        ListNode next = priorityQueue.peek();
        if (next == null) {
            p.next = node;
            break;
        }
        ListNode pNode = node;
        while (pNode.next != null && pNode.next.val <= next.val) {
            pNode = pNode.next;
        }
        if (pNode.next != null) {
            priorityQueue.add(pNode.next);
        }
        pNode.next = null;
        p.next = node;
        p = pNode;
    }
    return head.next;
}