23. 合并K个升序链表

题目

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

输入：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

解题思路

最小堆实现（优先队列思想）

优先队列是我首先想到的解题思路。因为每个链表都是有序的，因此维护一个最小堆存放头节点，每次出堆最小元素，然后再入队所在链表的下一个元素。
空间复杂度：最小堆成本，就是数组长度k
时间复杂度：优先队列插入和删除时间成本是logk，最多kn个点，也就是2kn次，因此总时间复杂度是nlogk

Java优先队列内部是最小堆实现的。

class Solution {
    PriorityQueue<Element> queue = new PriorityQueue<>();

    public ListNode mergeKLists(ListNode[] lists) {
        // 初始化优先队列
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(new Element(node));
            }
        }
        // 弹出最小元素，并入队新元素
        ListNode pre = new ListNode(-1);
        ListNode cur = pre;
        while (!queue.isEmpty()) {
            Element minE = queue.poll();
            if (minE.listNode.next != null) {
                queue.add(new Element(minE.listNode.next));
            }
            // 下一个值
            cur.next = minE.listNode;
            // 指针后移
            cur = cur.next;
        }
        return pre.next;
    }

    /**
     * 可以比较的元素
     */
    class Element implements Comparable<Element> {
        ListNode listNode;

        Element(ListNode listNode) {
            this.listNode = listNode;
        }

        @Override
        public int compareTo(Element o) {
            return this.listNode.val - o.listNode.val;
        }
    }
}

分治思想实现

几个有序的链表，第一时间没想起用分治来解决，真的是罪过。。
分治很好实现，不断拆分递归，基于链表两两合并。

空间复杂度：分治使用到虚拟机栈，logk
时间复杂度：比较两个链表是2n，也就是n。需要logk次，因此复杂度是nlogk。
与上面的优先队列差不多。

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    // 分治合并
    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1;
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    // 两两合并两个相邻链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 出于性能考虑的话，也可以先判断一次空
        ListNode pre = new ListNode(-1);
        ListNode tail = pre;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
               tail.next = list2;
               list2 = list2.next;
            }
            tail = tail.next;
        }
        // 剩余的部分
        tail.next = list1 != null ? list1 : list2;
        return pre.next;
    }
}