23. Merge k Sorted Lists
Problem Description
You are provided with an array that contains k
sorted linked lists. Each linked-list in the array is sorted in ascending order. Your task is to merge these k
sorted linked-lists into a single sorted linked-list. The final linked-list should continue to be sorted in ascending order and should include all the elements from the k
linked-lists.
Intuition
The solution to this problem makes use of a min-heap (also known as a priority queue in some languages) to efficiently merge the k
sorted linked-lists. Since each linked-list is sorted, the smallest element of the merge-list must be one of the k
heads of the input linked-lists.
Here's the step-by-step intuition behind the solution:
- First, we initialize a min-heap that will contain the current smallest node from each linked-list.
- We go through the list of linked-lists, and if a linked-list is not empty, we insert its head into the min-heap. Since we are dealing with a linked-list, we only need a reference to the head node to access the entire list.
- We create a new dummy node that serves as the precursor to the merged linked-list, which we'll build one node at a time as we extract the smallest nodes from the min-heap.
- While the min-heap is not empty, we perform the following steps:
- Extract the smallest node from the min-heap (this is done efficiently for a min-heap since the smallest element is always the root).
- If the extracted node has a next node, we insert the next node into the min-heap to replace the position of the extracted node.
- Append the extracted node to the merged linked-list by setting the
next
reference of the current node to this extracted node. - Move the current node pointer forward to this extracted node, which is now the last node in the merged list.
- Once we've exhausted all the nodes (when the min-heap is empty), we've built the complete merged linked-list which starts from the dummy node's next node.
- The use of the min-heap ensures that we're always processing nodes in ascending order since the heap is always sorted after each insertion and removal.
This approach is efficient because it doesn't require us to look at each node in every list when we're appending the smallest node. Instead, at any point in time, we're only comparing the current smallest nodes of each list.
Learn more about Linked List, Divide and Conquer, Heap (Priority Queue) and Merge Sort patterns.
Solution Approach
The code provided is a direct implementation of the intuition behind the solution using Python's built-in heap functionality. Let's walk through the implementation step by step:
-
The definition for the singly-linked list,
ListNode
, is provided. A__lt__
method is added to theListNode
class, which allows the comparison between twoListNode
instances based on theirval
attribute. This is required for the heap to maintain the correct order based on node values. -
The
mergeKLists
function is defined to take in the list of linked-lists. This function returns a merged sorted linked-list. -
A
pq
(priority queue) is initialized which will act as our min-heap. We use a list comprehension to include the head of each linked-list, provided it is not aNone
. -
The
heapify
function from theheapq
module is called onpq
, which transforms the list into a heap. In the context of a heap, the smallest element is always at the root, andheapify
ensures that the invariant of the heap is maintained. -
A
dummy
node is created. This dummy node serves as the starting point of our merged linked-list. Thedummy
node does not hold any data relevant to the final list but is used as a reference point. Acur
pointer is also created to keep track of the current end of the merged list. -
A
while
loop is used to iterate until the heappq
is empty.- We use
heappop
to remove and return the smallest node from the heap. Remember, this operation maintains the heap property after the removal. - We check if the node that was just popped off has a
next
node. If it does, thisnext
node is then pushed onto the heap usingheappush
. This ensures the next smallest node in that linked-list is now available for comparison. - The
cur
pointer'snext
is then set to this node, adding it to the final merged list. - We then advance
cur
to point to the node we just added to the merged list.
- We use
-
Once the heap is empty, we have added all the nodes to our merged list.
dummy.next
will be pointing to the head of the merged sorted linked-list. This is the result that we return from themergeKLists
function.
By using a min-heap, the solution ensures that at every step, the node with the smallest value among the k lists is chosen and added to the final list, which preserves the sorted order. The heap optimizes the process of finding the next smallest element, giving the algorithm a better time complexity compared to a naive approach of comparing every node in every list.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a simple example to illustrate the solution approach with k = 3
sorted linked lists:
Consider the following linked lists:
List 1: 1 -> 4 -> 5
List 2: 1 -> 3 -> 4
List 3: 2 -> 6
Step-by-step process:
-
Initialize Min-Heap: We start by creating an empty min-heap.
-
Insert Initial Nodes into Min-Heap: We insert the head of each non-empty linked list into the min-heap.
Min-heap:
[1, 1, 2]
(elements from List 1's head, List 2's head, and List 3's head) -
Create Dummy Node: We create a dummy node as a placeholder for the merged list's head.
-
Merge Process: We continuously remove the smallest element from the min-heap and append it to the merged list, then we add the next element from the same list to the min-heap (if there is one)
- Extract min (1 from List 1), min-heap is now
[1, 2, 4]
, and add the next element of List 1 (4) to min-heap. - Extract min (1 from List 2), min-heap is now
[2, 4, 4]
, and add the next element of List 2 (3) to min-heap. - Extract min (2 from List 3), min-heap is now
[3, 4, 4]
, no element to add as List 3's next is null. - Extract min (3 from List 2), min-heap is now
[4, 4, 5]
, and add the next element of List 2 (4) to min-heap. - Extract min (4 from List 2), continue the process until all elements are merged in the heap.
Merged list (in the process):
1 -> 1 -> 2 -> 3 -> 4 -> ... - Extract min (1 from List 1), min-heap is now
-
Completion: Once the min-heap is empty, all nodes have been added to the merged list.
Final merged list:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
By extracting the minimum element from the heap and maintaining each linked list's remaining nodes in the min-heap, we always have access to the current smallest nodes that need to be compared. This is how we merge efficiently and maintain the ascending order throughout.
Solution Implementation
1from queue import PriorityQueue
2
3# Class definition for a singly-linked list node.
4class ListNode:
5 def __init__(self, val=0, next=None):
6 self.val = val
7 self.next = next
8
9 # This ensures the PriorityQueue can compare ListNode objects by their 'val' attribute.
10 def __lt__(self, other):
11 return self.val < other.val
12
13class Solution:
14 def mergeKLists(self, lists):
15 """
16 Merge k sorted linked lists and return it as one sorted list.
17
18 :param lists: A list of ListNode objects, where each ListNode is the head of a sorted linked list.
19 :return: ListNode object that is the head of the merged sorted list.
20 """
21
22 # Priority queue initialized to hold the list nodes.
23 priority_queue = PriorityQueue()
24
25 # Adding the first node of each list to the priority queue.
26 for head in lists:
27 if head:
28 priority_queue.put(head)
29
30 # Creating a dummy node which will help in easily returning the head of the merged list.
31 dummy = current = ListNode()
32
33 # Extract nodes from the priority queue and build the merged list.
34 while not priority_queue.empty():
35 # Get the node with the smallest value.
36 node = priority_queue.get()
37
38 # If there's a next node in the list, add it to the priority queue.
39 if node.next:
40 priority_queue.put(node.next)
41
42 # Link the extracted node to the merged list and move the pointer.
43 current.next = node
44 current = current.next
45
46 return dummy.next
47
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int value;
6 ListNode next;
7
8 ListNode() {}
9 ListNode(int value) { this.value = value; }
10 ListNode(int value, ListNode next) { this.value = value; this.next = next; }
11}
12
13class Solution {
14 public ListNode mergeKLists(ListNode[] lists) {
15 // Initialize a min-heap (priority queue) to hold nodes and sort them by their value.
16 PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((node1, node2) -> node1.value - node2.value);
17
18 // Add the first node of each list to the priority queue, if it is not null.
19 for (ListNode head : lists) {
20 if (head != null) {
21 priorityQueue.offer(head);
22 }
23 }
24
25 // Create a dummy node that will serve as the head of the merged list.
26 ListNode dummyHead = new ListNode();
27 // A pointer to track the current node's position in the merged list.
28 ListNode current = dummyHead;
29
30 // Continue merging until the priority queue is empty.
31 while (!priorityQueue.isEmpty()) {
32 // Poll the priority queue to get the node with the smallest value.
33 ListNode smallestNode = priorityQueue.poll();
34
35 // If the smallest node has a next node, add it to the priority queue.
36 if (smallestNode.next != null) {
37 priorityQueue.offer(smallestNode.next);
38 }
39
40 // Connect the current node in the merged list to the smallest node.
41 current.next = smallestNode;
42 // Move the current pointer forward.
43 current = current.next;
44 }
45
46 // Return the merged list, skipping the dummy head.
47 return dummyHead.next;
48 }
49}
50
1// Definition for singly-linked list.
2struct ListNode {
3 int val;
4 ListNode *next;
5 ListNode() : val(0), next(nullptr) {}
6 ListNode(int x) : val(x), next(nullptr) {}
7 ListNode(int x, ListNode *next) : val(x), next(next) {}
8};
9
10class Solution {
11public:
12 ListNode* mergeKLists(vector<ListNode*>& lists) {
13 // Comparator for the priority queue: it will prioritize the node with the smaller value.
14 auto compare = [](ListNode* a, ListNode* b) {
15 return a->val > b->val;
16 };
17
18 // Define a priority queue with the custom comparator to keep track of the nodes.
19 priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> min_heap(compare);
20
21 // Add the first node of each list to the priority queue if it is not null.
22 for (ListNode* list_head : lists) {
23 if (list_head) {
24 min_heap.push(list_head);
25 }
26 }
27
28 // Create a dummy head for the result list.
29 ListNode* dummy_head = new ListNode();
30 ListNode* current_node = dummy_head;
31
32 // While the priority queue is not empty, extract the minimum element and link it to the current result list.
33 while (!min_heap.empty()) {
34 ListNode* min_node = min_heap.top();
35 min_heap.pop();
36
37 // If the extracted node has a next node, add it to the priority queue.
38 if (min_node->next) {
39 min_heap.push(min_node->next);
40 }
41
42 // Attach the minimum node to the current node of the result list and move forward.
43 current_node->next = min_node;
44 current_node = current_node->next;
45 }
46
47 // The next node of dummy_head points to the head of the merged list. Return this node.
48 return dummy_head->next;
49 }
50};
51
1// The ListNode class represents each node of a singly-linked list with a value and a link to the next node.
2class ListNode {
3 val: number;
4 next: ListNode | null;
5
6 constructor(val?: number, next?: ListNode | null) {
7 this.val = val === undefined ? 0 : val;
8 this.next = next === undefined ? null : next;
9 }
10}
11
12/**
13 * Merges k sorted linked lists into one sorted linked list and returns its head.
14 * Uses a minimum priority queue to determine the next smallest element to be added to the merged list.
15 * @param lists - An array of ListNode instances representing the heads of k sorted linked lists
16 * @returns A ListNode instance representing the head of the merged sorted linked list, or null if all lists are empty
17 */
18function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
19 // Initialize a minimum priority queue with a custom priority comparator based on ListNode's value
20 const minPriorityQueue = new MinPriorityQueue({ priority: (node: ListNode) => node.val });
21
22 // Enqueue the head of each non-empty list into the priority queue
23 for (const head of lists) {
24 if (head) {
25 minPriorityQueue.enqueue(head);
26 }
27 }
28
29 // Create a dummy head for the merged list
30 const dummyHead = new ListNode();
31 // 'current' keeps track of the last node in the merged list
32 let current: ListNode = dummyHead;
33
34 // Continue combining nodes until the priority queue is empty
35 while (!minPriorityQueue.isEmpty()) {
36 // Dequeue the smallest element and add it to the merged list
37 const node = minPriorityQueue.dequeue().element;
38 current.next = node;
39 current = current.next;
40
41 // If there is a next node in the dequeued element's list, enqueue it
42 if (node.next) {
43 minPriorityQueue.enqueue(node.next);
44 }
45 }
46
47 // Return the merged list, which starts at dummyHead's next node
48 return dummyHead.next;
49}
50
Time and Space Complexity
Time Complexity
The time complexity of the given code primarily involves the operations of heappush and heappop on the priority queue (min-heap) data structure, along with the initial construction of that queue.
-
Heapify: The initial heapification of the list
pq
, which contains at mostk
nodes (wherek
is the number of linked lists), has a complexity ofO(k)
because it is a linear time operation for building a heap from an existing list ofn
elements. -
While loop: The while loop, runs until the priority queue is empty. In the worst case, this will be equal to the total number of nodes in all input lists, which can be represented as
n*k
(if each list hasn
nodes). -
Heappop: Each heappop operation has a time complexity of
O(log k)
since, in the worst case, it may have to heapify a tree withk
nodes after removing the smallest element (root of the heap). -
Heappush: Each heappush operation also has a time complexity of
O(log k)
because it must maintain the heap property after inserting a new element into the heap.
Given there are n*k
elements to process in total and for each we potentially have a heappop and heappush operation, the overall time complexity is O(n*k*log k)
.
Space Complexity
-
Heap: The space complexity is determined by the size of the heap, which at maximum can hold
k
elements (one from each linked list). Hence, the space complexity isO(k)
. -
Output Linked List: The space for the output linked list does not count toward the space complexity since space complexity is typically analyzed with respect to additional space required by the algorithm, not including space needed for the output.
Thus, the space complexity is O(k)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.