23.合并 K 个升序链表

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

思路：

首先：该题使用java的PriorityQueue数据结构(PriorityQueue实质就是小根堆)，你add()一个数，PriorityQueue会自动排序，poll()一个数，会返回堆中的最小值。

大体流程：

• 遍历lists每个元素(每个元素就是一个链表)，将每个链表的头结点加入到小根堆中，然后首次poll()出来的就是lists所有链表中头最小的，拿它当做新链表的头。
• 然后判断该链表还有没有后继结点，如果有再加入到小根堆
• 再poll()出来一个，拼到新链表的后面，如果poll()的节点还有后继节点再加入，什么时候小根堆为空了

返回新链表

public class Problem_0023_MergeKSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a ,b) -> a.val - b.val);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.add(lists[i]);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode head = heap.poll();
        // pre负责拼接新链表
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;
    }
}