Binary Reduction

(Use ListNode as the examlple) Apply binary reduction to a group of lists.

Recursive (top down)

Space Complexity: O(lg(n)), n is the length of lists

public ListNode binaryReduction(ListNode[] lists, int s, int e) {
    // at the begining, s=0, e=lists.length-1
    if(s==e) return lists[s];
    int mid = s+(e-s)/2;
    ListNode n1 = binaryReduction(lists,s,mid);
    ListNode n2 = binaryReduction(lists,mid+1,e);
    lists[s] = reduceTwo(n1,n2);//method to reduce two lists.
}

Iterative (bottom up)

Space Complexity: O(1)

// Solution 2
public ListNode mergeKLists(ListNode[] lists) {
    int length = lists.length;
    for(int width = 1; width<length; width*=2){

        for(int i=0; i+width<length; i+=2*width) {
            int left = i, mid = i+width, right = i+2*width;
            // left: start point of first half; mid: start point of second half;
            // right: end point of the two part (exclusive)
            ListNode head = mergeTwoLists(lists[left],lists[mid]);
            lists[left] = head;
        }
    }
    return lists[0];
}

deprecated code

```java Solution 1 (deprecated) public ListNode mergeKLists(ListNode[] lists) { int totList = lists.length; if(totList==0) return null; while(totList>1) { //decrease by half layer by layer until it reaches 1. for(int i=0; 2*i

Similar Question

LeetCode 23. Merge k Sorted Lists