The next hard problem I want to tackle is merging of k sorted linked lists. An obvious way to solve this problem is by copying all the values from the k lists into a vector and sorting the vector. This is extremely inefficient both in terms in time and space complexity. If N1, N2, …, Nk are the sizes of each list, let’s call N = N1 + N2 + … + Nk. Then space complexity of such an approach would be O(N). Time complexity would be O(NlogN). Here’s this simple approach:

Naive approach

How could we do better? The main idea is to keep only one element from each list in a priority queue. After we do that, we can remove the smallest element from the priority queue. At the same time, we add another element from the same list we got the smallest element from if it still has more elements. We keep doing this operation till we exhaust all the elements. In some sense, we are using priority queue to keep k pointers into the k lists.

How to keep track of which list a list node came from? We create a struct with two fields as follows:

Now, we simply add this Node to the priority queue. But to be able to use this custom struct with the priority queue, we need to define a custom operator for <. This can be done as follows:

A better approach

With these two ideas, we can easily solve this problem as follows:

Fill up the priority queue with one value from each list

Iterate till the priority queue is empty

Each step, remove the smallest node

If we don’t have head set, set the node as head

If we have a previous node, point the previous node to this node

Find out which list this node came from

Add the next element from that list (if one exists) to the priority queue

Return head

Note we could have also used a similar approach to the vertical order traversal problem for storing the data using a std::tuple. I intentionally used a different approach to showcase the use of a custom node in a priority queue. This approach makes the ordering obvious.

Update: 2023/10/30

After writing this post, I realized I don’t need to store the index of the list in the priority queue after all. With that realization, I came up with the following more compact implementation: