# A java optimal solution based on loser tree

• I used loser tree to solve this problem. The time complexity was O((n-1)*logk), and the extra space required by loser tree is int[k]. If you have any question about my algorithm, please let me know.

By the way , I found a bun in the default algorithm that used in test cases. You can repeat it with the input "[[6,10,33,2147483647,2147483647],[-2147483648,-2147483648,10, 18,20,33,38],[-2147483648, 2,3,10,15, 55]]". The default algorithm return wrong result [6,10,33,2147483647,2147483647,-2147483648,2,3,10,15,55,-2147483648,-2147483648,10,18,20,33,38], but the correct result is [-2147483648,-2147483648,-2147483648,2,3,6,10,10,10,15,18,20,33,33,38,55,2147483647,2147483647].

`````` public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<ListNode> newLists = new ArrayList<ListNode>();
for(ListNode node : lists) {
if (node != null) {
}
}
if(newLists.size() == 0) {
return null;
}
if (newLists.size() == 1) {
return newLists.get(0);
}
int k = newLists.size();
// 0 - winner, 1~k-1:loser, k+1: MIN_VALUE
int[] a = new int[k];
ListNode[] b = new ListNode[k+1];
b[k] = new ListNode(Integer.MIN_VALUE);
for (int i = 0; i< k; i++) {
a[i] = k;
b[i] = newLists.get(i);
}

// init loser tree
for (int i = k-1; i >= 0; i--) {
}

int finishedCount = 0;
while(finishedCount < k) {
int winner = a[0];
cur.next = b[winner];
cur = cur.next;
if (cur.next != null) {
b[winner] = cur.next;
} else {
b[winner] = new ListNode(Integer.MAX_VALUE);
finishedCount ++;
}
}

}

private void adjust(int[] a, int winner, ListNode[] lists) {
int curP = winner;
int k = lists.length -1 ;
for (int i = (k+winner)/2; i > 0; i = i/2) {
// parent is winner, set curP to the loser node(a[i]), and set parent node(old a[i] value) to curP
if(lists[a[i]].val <= lists[curP].val) {
int tmp = a[i];
a[i] = curP;
curP = tmp;
}
}
a[0] = curP;
}

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.