题目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

解法一 归并排序

延续昨天的思路，看到提供的是有序的链表，要对两个有序链表进行排序合并，可以使用归并排序。

用preResult来指示每次合并后新的目标链表。直到每个链表都合并进去为止。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 递归结束条件
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        // 这不就是归并排序？ 
        // 归并排序, 目标链表是lists[0]
        ListNode left = lists[0], preResult = new ListNode(0);
        for (int i = 1; i < lists.length; i++) {
            ListNode right = lists[i], tempNode = preResult;
            while (right != null && left != null) {
                tempNode.next = left.val <= right.val ? left : right;
                tempNode = tempNode.next;
                if (left.val <= right.val) {
                    left = left.next;
                } else {
                    right = right.next;
                }
                tempNode.next = null;
            }
            tempNode.next = right != null ? right : left;
            left = preResult.next;
        }
        return preResult.next;
    }
}

时间复杂度：第一个链表参与k次，第二个链表k-1次…第k个链表1次。平均每个节点参与到O(k)次合并中(1+2+⋯+k)/k 。所以总的时间复杂度为O(nk)。这个耗时是比较长的。

解法二 小根堆

最小堆是一种特殊的二叉堆结构，其中每个节点的值都小于或等于其子节点的值，使得堆顶（根节点）始终是最小值。在Java中，可以通过PriorityQueue类实现最小堆，因为PriorityQueue默认就是最小堆结构。

这里可以将所有链表元素入小根堆，然后一个一个poll出来，因为每个元素入堆和出堆的时间复杂度为O(logn)，这样总的时间复杂度为O(nlogn)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
        int cnt = 0;
        for (ListNode node : lists) {
            while (node != null) {
                queue.add(node);
                node = node.next;
                cnt++;
            }
        }
        ListNode dummy = new ListNode(0), sign = dummy;
        while (cnt != 0) {
            sign.next = queue.poll();
            sign = sign.next;
            cnt--;
        }
        sign.next = null;
        return dummy.next;
    }
}

优化

因为每次取最小的一定是从每个链表的表头取最小的，所以可以将小根堆优化成只存储每个链表头的堆，高度为logk（k为数组中链表数量）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) queue.add(node);
        }
        ListNode dummy = new ListNode(0), sign = dummy;
        while (!queue.isEmpty()) {
            sign.next = queue.poll();
            sign = sign.next;
            if (sign.next != null) queue.add(sign.next);
        }
        return dummy.next;
    }
}

时间复杂度优化为O(nlogk).