思路 + 解题过程

分治合并

与 LeetCode 21题 合并两个有序链表 相似 只是在此题的基础上增加了链表的数量。

使用递归将链表数组不断分成两半，直到分成的小组都只剩下一个链表元素为止，随后开始合并链表。

复杂度

• 时间复杂度: O(N * logK) K 为 链表(lists) 的个数，n 为所有链表的节点数之和。

• 空间复杂度: O(logK) 递归的深度为 logK

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;

        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end)
            return lists[start];

        int mid = (start + end) >>> 1;
        ListNode pa = merge(lists, start, mid);
        ListNode pb = merge(lists, mid + 1, end);
        return mergeSort(pa, pb);
    }

    public ListNode mergeSort(ListNode pa, ListNode pb) {
        ListNode target = new ListNode(0);
        ListNode temp = target;

        while(pa != null && pb != null){
            if(pa.val < pb.val){
                temp.next = pa;
                pa = pa.next;
            }else{
                temp.next = pb;
                pb = pb.next;
            }
            temp = temp.next;
        }

        temp.next = pa != null ? pa : pb; 

        return target.next;
    }
}

        也可以通过for循环遍历的方式依次合并链表，不过时间复杂度会有所提升。