# Binary Merge Sort (16ms) beats 83.72% java submissions

• if your java code just merge the ListNode one by one without priority queue, you may easily get TLE .
why ? Because I tried it many times (cry) and its complexity is O(n^3).So I have to use the binary merge and it is O(logN * n^2) ---- every merge is O(n^2) and there are logN combination.

``````public class Solution {

public ListNode mergeKLists(ListNode[] lists) {

ListNode result = null;
if(lists == null || lists.length < 1)return result;
if(lists.length == 1)return lists[0];

result = binaryMerge(lists, 0, lists.length-1);
return result;
}

//simple binary merge
public ListNode binaryMerge(ListNode[] lists, int left, int right){

if(lists == null || lists.length <= 0)return null;
if(lists.length == 1)return lists[0];
if(left == right)return lists[left];

if(right - left == 1){
return mergeTwoLists(lists[left], lists[right]);
}else{
int mid = (right + left) / 2;
ListNode leftNode = null;
ListNode rightNode = null;
if(left <= mid)leftNode = binaryMerge(lists, left, mid);
if(right >= mid+1)rightNode = binaryMerge(lists, mid+1, right);
return mergeTwoLists(leftNode, rightNode);
}
}

//merge two list
public ListNode mergeTwoLists(ListNode list1, ListNode list2){

if(list1 == null && list2 == null)return null;
if(list1 == null && list2 != null)return list2;
if(list1 != null && list2 == null)return list1;

ListNode l1Temp = list1;
ListNode l2Temp = list2;

while(l1Temp != null && l2Temp != null){

if(l1Temp.val >= l2Temp.val){
if(resTemp == null){
resTemp = l2Temp;
l2Temp = l2Temp.next;
}else{
resTemp.next = l2Temp;
resTemp = l2Temp;
l2Temp = l2Temp.next;
}
}else{
if(resTemp == null){
resTemp = l1Temp;
l1Temp = l1Temp.next;
}else{
resTemp.next = l1Temp;
resTemp = l1Temp;
l1Temp = l1Temp.next;
}
}
}

while(l1Temp != null){
resTemp.next = l1Temp;
resTemp = l1Temp;
l1Temp = l1Temp.next;
}

while(l2Temp != null){
resTemp.next = l2Temp;
resTemp = l2Temp;
l2Temp = l2Temp.next;
}
}
}
``````

• Same idea, but beats 99% java submissions. May be my mergeTwoLists more efficient.

``````
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null)
return null;
if (lists.length < 2)
return lists.length == 0 ? null : lists[0];
int middle = lists.length / 2 - 1;
return mergeTwoLists(mergeSubLists(lists, 0, middle), mergeSubLists(lists, middle + 1, lists.length - 1));
}

private ListNode mergeSubLists(ListNode[] lists, int from, int to) {
if (to == from)
return lists[from];
if ((to - from) == 1)
return mergeTwoLists(lists[from], lists[to]);
int middle = from + (to - from) / 2;
return mergeTwoLists(mergeSubLists(lists, from, middle), mergeSubLists(lists, middle + 1, to));
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null)
return l1 == null ? l2 : l1;
ListNode tail = null;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
if (tail != null)
tail.next = l1;
else
tail = l1;
l1 = l1.next;
} else {
if (tail != null)
tail.next = l2;
else