Cracking the Coding Interview: Merge K sorted Lists.

This is another hard level leetcode problem commonly asked during coding interviews. To be able to solve this problem you first need to know how to solve the Merge Two sorted lists problem.Therefore make sure you check my approach of solving the merge two sorted lists problem first before going into this problem.

The Question:

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

Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

The brute force solution that someone would definitely first think about when it comes to solving this problem is to traverse all the linked lists and then collect all the values into an array. Afterwards you sort and iterate over this array to create a proper value of the nodes and then create a new sorted linked list with the new Nodes.

Here is the brute force solution in code:

brute force solution

Time complexity is O(n log n) while space complexity is O(n)

Approach 2:

We can as well solve this by adding on our previous solution to merge two sorted lists whereby we will create a helper merge function(the merge 2 sorted lists function) and then divide our k lists into two lists and then merge them. Here is the approach in code:

Approach 3:

This is a more optimal way of solving this problem.

You get to compare every k node, every head of the linked list and get the node with the smallest value. You then afterwards extend the final sorted linked list with the selected nodes. You can do this through the use of Priority Queues and also min heaps.

Using Priority Queues code approach.

using priority queues

Time complexity: O(n log k)

Using min heap code approach

using min heaps

I hope that this article has given you a picture of how to approach this problem during coding interviews.

See you on the next coding problem!