Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Merge k sorted linked lists and return it as one sorted list

Sharing is caring!

Problem statement
Merge k sorted linked lists and return it as one sorted list.

Solution
We reduce the problem to the merging of two linked lists problem. This can be done in \mathcal{O}(n) time and \mathcal{O}(1) space. So we first write out the function to merge two sorted lists:

We can then go on and iterate over all the lists and merge them in pairs. We will merge the first two lists and then merge the resulting list with the subsequent list in the array. The use that result and merge it with the next un visited list and so on.

Full code