hot100_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 = [[]]
输出：[]

思路

顺序合并

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

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for(int i=0;i<lists.length;++i){
            ans = mergeList(ans,lists[i]);
        }
        return ans;
    }
    public ListNode mergeList(ListNode a,ListNode b){
        if(a==null || b==null){
            return a != null ? a:b;
        }
        ListNode head = new ListNode(0);
        ListNode temp = head,temp1 = a,temp2 = b;
        while(temp1!=null && temp2!=null){
            if(temp1.val <temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            } else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if(temp1!=null){
            temp.next = temp1;
        } else{
            
            temp.next = temp2;
        }
        return head.next;
    }

}

分而治之

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

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

    return mergeList(merge(lists,l,mid),merge(lists,mid+1,r));    这里的mid+1,r是容易错的

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;
        return mergeList(merge(lists,l,mid),merge(lists,mid+1,r));
    }

    public ListNode mergeList(ListNode a,ListNode b){
        if(a==null || b==null){
            return a != null ? a:b;
        }
        ListNode head = new ListNode(0);
        ListNode temp = head,temp1 = a,temp2 = b;
        while(temp1!=null && temp2!=null){
            if(temp1.val <temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            } else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if(temp1!=null){
            temp.next = temp1;
        } else{
            
            temp.next = temp2;
        }
        return head.next;
    }

}