Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
We can use a
vector to collect all the nodes, and sort according to the values, then iterator the vector to construct a new
Time complexity: $O(NlogN)$, where N is the number of all
ListNode. Space complexity: $(N)$.
Optimization with a priority queue
Another naive solution is also obvious, we can use
K pointers to track the current pointer of each
LinkList, iterate these pointers to find the minimum pointer in each round, extend the selected node to result.
Can we do better on time performance?
The answer is yes, we can use a priority queue to track the pointers. So that we don’t need to iterate
K pointers in each round, instead we fetch the top node from the priority queue.
Time complexity: $O(NlogK) where
N is the sum number of nodes, and
K is the
lists.size. This will be much better than the previous solution because
K is smaller than
N in most cases.
Space complexity: $O(N)$ and extra $(k)$ for priority queue.
Preparing for an interview? Check out this!