[LeetCode] 23. Merge k Sorted Lists

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

Sol. Divide and conquer. Merge 2 lists each time.

(source: Solution on LeetCode)

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        for (int interval = 1; interval < lists.length; interval *= 2) {
            for (int i = 0; i < lists.length - interval; i += interval * 2) {
                lists[i] = merge2Lists(lists[i], lists[i + interval]);
            }
        }
        return lists[0];
    }
    
    ListNode merge2Lists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
            
        if (l1.val < l2.val) {
            l1.next = merge2Lists(l1.next, l2);
            return l1;
        }
        
        l2.next = merge2Lists(l1, l2.next);
        return l2;
    }

Time Complexity: O(N log k). k is the number of lists. Traverse almost $N$nodes per pairing and merging, and repeat this procedure about 
$\log_{2}{k}$ times.

Space Complexity: O(1). Use interval to record the merging state.