23. Merge k Sorted Lists

HardLinked ListDivide and ConquerHeap (Priority Queue)Merge Sort
Leetcode Link

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:

  1. First, we initialize a min-heap that will contain the current smallest node from each linked-list.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

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:

  1. The definition for the singly-linked list, ListNode, is provided. A __lt__ method is added to the ListNode class, which allows the comparison between two ListNode instances based on their val attribute. This is required for the heap to maintain the correct order based on node values.

  2. The mergeKLists function is defined to take in the list of linked-lists. This function returns a merged sorted linked-list.

  3. 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 a None.

  4. The heapify function from the heapq module is called on pq, which transforms the list into a heap. In the context of a heap, the smallest element is always at the root, and heapify ensures that the invariant of the heap is maintained.

  5. A dummy node is created. This dummy node serves as the starting point of our merged linked-list. The dummy node does not hold any data relevant to the final list but is used as a reference point. A cur pointer is also created to keep track of the current end of the merged list.

  6. A while loop is used to iterate until the heap pq 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, this next node is then pushed onto the heap using heappush. This ensures the next smallest node in that linked-list is now available for comparison.
    • The cur pointer's next 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.

  7. 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 the mergeKLists 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example 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:

  1. Initialize Min-Heap: We start by creating an empty min-heap.

  2. 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)

  3. Create Dummy Node: We create a dummy node as a placeholder for the merged list's head.

  4. 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 -> ...

  5. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which data structure is used to implement priority queue?

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 most k nodes (where k is the number of linked lists), has a complexity of O(k) because it is a linear time operation for building a heap from an existing list of n 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 has n 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 with k 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 is O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Linked List Cycle

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

Divide and Conquer Intro

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

Heap Fundamentals

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 Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ