LeetCode 23 链表 Merge k Sorted Lists

LeetCode

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example：

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

代码：
暴力解法，依次取第一个最小的出来。这个适合多个流输入时的解法，复杂度为k^2N

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int index = minNode(lists);
        while(index != -1){
            cur.next = lists[index];
            lists[index] = lists[index].next;
            cur = cur.next;
            index = minNode(lists);
        }
        return head.next;
    }
    private int minNode(ListNode[] lists){
        int min = Integer.MAX_VALUE;
        int index = -1;
        for(int i = 0; i < lists.length; i++){
            ListNode tmp = lists[i];
            if(tmp != null && tmp.val < min){
                min = tmp.val;
                index = i;
            }
        }
        return index;
    }
}

分治归并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        if(lists.length == 1) return lists[0];
        if(lists.length == 2){
            return mergeTwoList(lists[0], lists[1]);
        }
        int mid = lists.length / 2;
        ListNode[] list1 = new ListNode[mid];
        ListNode[] list2 = new ListNode[lists.length - mid];
        for(int i = 0; i < mid; i++){
            list1[i] = lists[i];
        }
        for(int i = mid; i < lists.length; i++){
            list2[i - mid] = lists[i];
        }
        ListNode l1 = mergeKLists(list1);
        ListNode l2 = mergeKLists(list2);
        return mergeTwoList(l1, l2);
    }
    private ListNode mergeTwoList(ListNode list1, ListNode list2){
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode head = new ListNode(0);
        ListNode res = head;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                head.next = list1;
                list1 = list1.next;
            }else{
                head.next = list2;
                list2 = list2.next;
            }
            head = head.next;
        }
        if(list1 != null)
            head.next = list1;
        if(list2 != null)
            head.next = list2;
        return res.next;
    }
}

注意：