# Two ways. One is minHeap, the other is mergeSort way(recursion, faster)

• minHeap: time - O(nlog(k)), space - O(k), n is total number of all the listnode, k is the length of lists

public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return heap(lists);
}
private ListNode heap(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return a.val - b.val;
}
});
for (ListNode head : lists) {
}
ListNode res = new ListNode(0);
while (!pq.isEmpty()) {
ListNode cur = pq.poll();
res.next = cur;
res = res.next;
if (cur.next != null) {
pq.offer(cur.next);
}
}
}

like mergeSort(recursion): time-O(vlog(k)), space- O(log(k)), v is average length of a list, k is length of lists.

public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return helper(lists, 0, lists.length - 1);
}
private ListNode helper(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
}
int mid = (start + end) / 2;
ListNode left = helper(lists, start, mid);
ListNode right = helper(lists, mid + 1, end);
return mergeTwo(left, right);
}
private ListNode mergeTwo(ListNode left, ListNode right) {
while (left != null && right != null) {
if (left.val  <= right.val) {
left = left.next;
} else {
right = right.next;
}
}
if (left != null) {
}
if (right != null) {
}
}

• @daniel123 No really. For the divide & conquer merge, after every loop, although the number of listnode is halved, the average length of each listnode is doubled. So it is still O(nklog(k)), n being the original average length.

• @ayuanx There are log(k) levels. On each level, there are always N nodes in total. So the complexity is O(Nlog(k));

• @kotomi_null Think again. Every two N nodes merged together, you get 2*N nodes. So every level up, the number of nodes in each list doubles.

• @ayuanx Let me rephrase, N is the total number of all nodes, not the average length of a list. Let say list A has 20 nodes and, B 10, C 20, D 10. N = 60 here. We merge A and B, C and D at bottom level. There will be (10 + 20) + (10 + 20) = 60 = N ops on this level. Then we merge A-B and C-D (each list has 30 nodes now). There are still 30 + 30 = N ops.

Is that clear now? If not, you could draw a tree and count ops yourself. Thanks

• @kotomi_null Then we are talking about the same thing.
The symbols I use are:
n: average length of each list.
k: number of lists.
So the total number of nodes == n*k, which is actaully your N.

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