# My simple java Solution use recursion

• ``````public static ListNode mergeKLists(ListNode[] lists){
return partion(lists,0,lists.length-1);
}

public static ListNode partion(ListNode[] lists,int s,int e){
if(s==e)  return lists[s];
if(s<e){
int q=(s+e)/2;
ListNode l1=partion(lists,s,q);
ListNode l2=partion(lists,q+1,e);
return merge(l1,l2);
}else
return null;
}

//This function is from Merge Two Sorted Lists.
public static ListNode merge(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next=merge(l1.next,l2);
return l1;
}else{
l2.next=merge(l1,l2.next);
return l2;
}
}``````

• to avoid integer overflow, use q = s + (e -s) / 2 instead

• Thanks for the excellent solution

• is the time complexity?

• It is O(nlgn).

• nlogk where k is the number of lists and n is total number of nodes.

• @yanggao, no need. s,q are indexes

• I did the same implementation as you. This is 3ms beating 93%

``````public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mL(lists, 0, lists.length - 1);
}

private ListNode mL(ListNode[] lists, int l, int r) {
if (r < l) return null;
if (r == l) return lists[r];

int mid = (l + r) / 2;
ListNode a = mL(lists, l, mid), b = mL(lists, mid + 1, r);
while (a != null && b != null) {
if (a.val < b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = (a != null) ? a : b;

}
}``````

• good answer. reminds me of merge sort

• The complexity is O(nk), it's not O(nlogk). Stop saying it's O(nLogK) please.
This is same as following:
get two listNodes -> merge them -> put merged result into original list.
It consumes one List node every time until it only has one ListNode

• No, it is O(nlogk), merge takes O(n) time and partition takes O(logk) time

• @spritmouselet
you are wrong ! it should be O(nlogk), becasue we mergered k sorted lists. so we do need merge them from one length lists.

• can anyone tell me why this solution is faster than priorityqueue?

• @daiqiang1117
The complexity for priority queue and this method is same i.e. nlogk. Because in priority queue you will make some n additions ( assuming n nodes ) for a list length of k.

• @shilpa6
Now I think the answer is quite clear. Use PQ, both poll and offer are logK operations.
So PQ solution comes out (n * 2 * logK)
However divide conquer is (n * logk)

• Isn't the time complexity o(nklogn) where k is avg length of linked list??

• Isn't the time complexity o(nklogn) where k is avg length of linked list??

• Yes. The complexity of this algorithm is o(nklogn)

• Sorry. The complexity is O(nklogk).

• @Manojbattula Some people say this recursion method is O(nlogk), while others say O(nklogk)I think it depends the how you define your n. In a previous answer, it is defined as TOTAL number of nodes, which already considering k...So I think all of you are correct.

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