题目：

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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

解法：

上一题是合并两个有序链表，如果是合并三个，那么可以先将两个链表合并，再将合并后的链表与第三个链表合并，算法的主体还是两个链表的合并。

方法一：顺序合并

最朴素的一个方法：用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 ii个链表和 ans 合并，答案保存到 ans 中。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //ListNode cur = new ListNode(0);
        //ListNode ans = cur.next;
        ListNode ans = null;
        int n = lists.length;
        for(int i = 0; i <n; i++){
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur = new ListNode(0);
        ListNode ans = cur;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        //合并list1和list2后最多只有一个还未被合并完，因此直接将链表末尾指向未合并完的链表即可
        cur.next = list1 == null ? list2 : list1;
        return ans.next; 
    }
}

复杂度分析

时间复杂度：假设每个链表的最长长度是 n。在第一次合并后，ans 的长度为 n；第二次合并后，ans 的长度为 2×n，第 i 次合并后，ans 的长度为 i×n。第 i 次合并的时间代价是 O(n + (i - 1) n) = O(i n)，那么总的时间代价为 ， 故渐进时间复杂度为。

空间复杂度：没有用到与 k 和 n 规模相关的辅助空间，故渐进空间复杂度为 O(1)。

方法二：分治合并

考虑优化方法一，用分治的方法进行合并。

将 k 个链表配对并将同一对中的链表合并；第一轮合并以后， k 个链表被合并成了 k/2 个链表，平均长度为 2n/k，然后是 k/4个 链表， k/8 个链表等等；
重复这一过程，直到我们得到了最终的有序链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l, int r){
        if(l == r){
            return lists[l];
        }
        if(l > r){
            return null;
        }
        int mid = (l + r) >> 1;//二进制向右移动一位，相当于除以2取整
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid+1, r));
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur = new ListNode(0);
        ListNode ans = cur;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        //合并list1和list2后最多只有一个还未被合并完，因此直接将链表末尾指向未合并完的链表即可
        cur.next = list1 == null ? list2 : list1;
        return ans.next; 
    }
}

复杂度分析

时间复杂度：考虑递归「向上回升」的过程——第一轮合并 k/2 组链表，每一组的时间代价是 O(2n)；第二轮合并 k/4 组链表，每一组的时间代价是 O(4n)……所以总的时间代价是 ，故渐进时间复杂度为 。
空间复杂度：递归会使用到 O(logk) 空间代价的栈空间。