23.Merge k Sorted Lists

1- Divide and Conquer

I think my code’s complexity is also_O(nlogk)_and not using heap or priority queue, n means the total elements and k means the size of list.

The mergeTwoLists functiony in my code comes from the problemMerge Two Sorted Listswhose complexity obviously isO(n), n is the sum of length of l1 and l2.

To put it simpler, assume the k is 2^x, So the progress of combination is like a full binary tree, from bottom to top. So on every level of tree, the combination complexity is n, beacause every level have all n numbers without repetition. The level of tree is x, ie logk. So the complexity isO(nlogk).

for example, 8 ListNode, and the length of every ListNode is x1, x2,
x3, x4, x5, x6, x7, x8, total is n.

on level 3: x1+x2, x3+x4, x5+x6, x7+x8 sum: n

on level 2: x1+x2+x3+x4, x5+x6+x7+x8 sum: n

on level 1: x1+x2+x3+x4+x5+x6+x7+x8 sum: n

total 3n, nlog8

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoList(ListNode l1, ListNode l2){
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        ListNode preHead = new ListNode(-1);
        ListNode tmp = preHead;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                tmp.next = l1;
                l1 = l1.next;
                tmp = tmp.next;
            }
            else{
                tmp.next = l2;
                l2 = l2.next;
                tmp = tmp.next;
            }
        }
        if(l1 != null)
            tmp.next = l1;
        if(l2 != null)
            tmp.next = l2;
        return preHead.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if(n == 0)
            return null;
        if(n == 1)
            return lists[0];
        if(n == 2)
            return mergeTwoList(lists[0], lists[1]);
        int half = n / 2;
        ListNode[] l1 = new ListNode[half] ;
        ListNode[] l2 = new ListNode[n - half];
        for(int i = 0; i < half; i++){
            l1[i] = lists[i];
        }
        for(int i = 0, j = half; j < n; i++, j++){
            l2[i] = lists[j];
        }
        return mergeTwoList(mergeKLists(l1), mergeKLists(l2));
    }
}