leetcode 23. 合并K个排序链表（Java版）

题目描述（题目难度，困难）

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

示例代码

解法一：

借助优先队列（小根堆），下面解法的时间复杂度为 ，k 为链表个数，n 为总的结点数，空间复杂度为 ，小根堆需要维护一个长度为 k 的数组。
时间复杂度分析：有 k 个结点的完全二叉树，高度为 ，每次弹出堆顶元素和插入元素重新调整堆的时间复杂度都为 ，所以总的时间复杂度为 。分析的比较粗略，不是精确的时间复杂度，不过大 O 表示法本身就是一个粗略的量级的时间复杂度表示，这样就足够了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {

            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
            
        });
        for(ListNode e : lists){
            if(e != null){
                pq.add(e);
            }
        }
        ListNode head = new ListNode(0);
        head.next = null;
        ListNode tail = head;
        while(!pq.isEmpty()){
            tail.next = pq.poll();
            tail = tail.next;
            if(tail.next != null){
                pq.add(tail.next);              
            }
            tail.next = null;
        }
        return head.next;
    }
}

解法二：

类似归并排序的回溯过程，两两合并。下面解法的时间复杂度也为 ，k 为链表个数，n 为总的结点数，空间复杂度为 。
时间复杂度分析：两两归并，每个结点会被归并 次，所以总的时间复杂度为 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 借助归并排序的思想，只有治没有分
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode res = new ListNode(0);
        ListNode tail = res;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                tail.next = l1;
                l1 = l1.next;
            }else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if(l1 != null){
            tail.next = l1;
        }else{
            tail.next = l2;
        }
        return res.next;
    }
    // 原地归并，并不申请新的数组空间，算法实现上，其实是找规律。
    public ListNode mergeKLists(ListNode[] lists) {
        // 步长为 2 时，和后面的第 1 个合并
        // 步长为 4 时，和后面的第 2 个合并
        // ...
        if(lists == null){
            return null;
        }
        int len = lists.length;
        int interval = 1;
        while(interval < len){
            for(int i = 0; i+interval < len; i += 2*interval){
                lists[i] = merge(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }
        return len != 0 ? lists[0] : null;
    }
}

思路解析

对于解法一：
由于我们很熟悉两个有序链表的合并，每次两两比较，将较小值合并进最终的有序链表。问题推广到 k 个有序链表的合并，我们自然而然的可以想到，每次比较 k 个值，将其中最小的合并进最终的有序链表。所以我们可以使用一个优先队列（小根堆）来维护 k 个结点的大小信息，而不需要每次从头开始比较 k 个结点的大小。

对于解法二：
k 个有序链表合并这个问题，可以看作是归并排序回溯过程中的一个状态，使用分治的思想求解，不过和归并排序不同的是，这里只有治而没有分。
下面这个图详细体现了算法过程，并且我们可以原地归并，不需要申请新的数组空间：

image.png
原地归并的算法实现，其实就是一个找规律问题。第一轮的归并是，0 和 1，2 和 3，4 和 5 ...；第二轮的归并是，0 和 2，4 和 6 ...；第三轮的归并是，0 和 4，4 和 8 ...；... 直到两归并链表的间距大于等于数组长度为止。