23. Merge k Sorted Lists

Leetcode #: 23
Name: Merge k Sorted Lists
Difficulty: Hard
Companies asked: Amazon, Apple, Google, LinkedIn, Meta, Microsoft, and Salesforce
Link: https://leetcode.com/problems/merge-k-sorted-lists/

Prompt

You are given an array of k linked-lists called lists and each of the k linked-list is sorted in ascending order. Your task is to merge all of these k linked-lists together into 1 final sorted linked-list and return it.

Approach

We have to remember that the provided array lists is an array that contains linked-lists as its elements. According to the ListNode class that is provided to you by default, Leetcode provides you with the definition for a singly-linked list. Therefore, I’ll be implementing the approach given that we are working with a singly-linked list, not a doubly-linked list. Furthermore, to traverse through a singly linked-list, we must start from its head as opposed to an array where we can iterate at any point in an array as long as we know the index or range of indices that we want to access.

We should iterate through each of the linked-lists within the lists array and traverse through each of the linked-lists starting from their head nodes and add every nodes’ values to a data structure. Which data structure should we add these nodes’ values to? Well, in this case, we want to return a final sorted linked-list in ascending order. Therefore, we want to use an advanced data structure that will provide us with the minimum value. From an abstract point of view, you can think of data structures almost like black boxes where we have special methods that we can execute unique to each data structure. In this case, we want a black box or data structure that has a special method in which when invoked, provides us with the minimum element or value from the data that we store in it. Ultimately, this data structure would be a min-heap as the minimum element in the min-heap would be located at its root node.

As we iterate through each linked-list within the given lists array, we want to add each node within each linked-list to the min-heap. Afterward, we can create a dummy node and create a tail pointer that will be pointing to the dummy node at the start. As long as we have elements in our min-heap, we want to call our black box’s special method (in this case, extracting the minimum element from the min-heap) and create a new node, assigning the node’s value to be the extracted minimum value. Then, we want to connect this new node with the dummy node and continue to repeat this process of creating a new node and assigning it with the next minimum value until the length of the min-heap is empty. At that point, we know that we added all of the nodes from each linked list from the given lists array.

Lastly, we want to return not the dummy node but its next property as our final sorted linked-list in ascending order would start from the node next of the dummy node. This is because we don’t want to include the dummy node in our final answer.

Code

Python

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub