[LeetCode] Merge k Sorted Lists (Java)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.


At first I thought this problem was quite easy. We can just pick the smallest one from all heads of lists and then connect it to the final list. But the complexity of this algorithm will be O(n2k), in which n is the number of lists and k is the average number of nodes in one list. However, my code passed the OJ at that time. This algorithm can be TLE easily, so it needs to be improved.

There are two ways to do this.

The first one is the recursive version. It’s similar to merge sort. For example, assuming we have 4 lists: 1, 2, 3, 4. We can merge 1 and 2 to be a new list 5. And 3 and 4 can be merged to be a new list 6. Finally we merge 5 and 6 to get the result. So in this algorithm, we divide the lists by 2 until its size reaches 1. And then merge them from bottom to top.

The second one is to use a priority queue. We can add the heads of all lists in to the queue. And we can poll out the smallest one. If the next node of this smallest node is not null, we can add the next node to the queue. We will continue doing this until the queue is empty.


Recursive version

 Priority queue version


Recursive version: We have T(n) = 2T(n/2) + kn. So the complexity is O(kn logn). The depth of the recursive function is O(log n).

Priority queue version: Every time we add a new element to the queue, it costs O(log n). And we have kn elements. So the complexity is O(kn logn) + O(kn) = O(kn logn). And the space complexity is only $O(n)$.