(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
