Start learning free

LESSON 281 OF 343 · LINKED LISTS

Merge K Sorted Lists in C++: O(n log k) with a Min-Heap

Practice O(N log k) Read the full explanation

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Note:

Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the total number of nodes across all lists and k is the number of lists.


Hints:

The brute force re-scans every list head each time. What data structure gives you the smallest of k values in O(log k) instead of O(k)?

Use a min-heap seeded with the head of every non-empty list, ordered by node.val.
Each iteration: extract the smallest node, append a copy of its value to the merged tail, and if it has a successor, push that successor onto the heap.
When the heap is empty, every list has been fully consumed.

The heap holds at most k nodes at any time. Each of the n output nodes costs one extract and at most one insert, each O(log k) — Time Complexity is O(n log k).
The heap itself uses O(k) extra space.

STEP 1 OF 12
    Ctrl + Enter to check

    C++ · LINKED LISTS

    Merge K Sorted Lists in C++, explained

    Problem overview

    The function mergeKLists receives a vector lists of k singly linked lists, each sorted in ascending order. Each node is a ListNode with an int val and a ListNode* next. The function returns the head of one sorted list that contains all the values.

    For lists = [[1,4,5],[1,3,4],[2,6]] the result is 1->1->2->3->4->4->5->6. The vector can be empty, which gives an empty list, and some of the lists can be empty too. In C++ an empty list is a null pointer.

    The statement asks for O(n log k) time, where n is the total number of nodes, and O(k) extra working space for the algorithm itself.

    Approach: always take the smallest head

    At any moment, the smallest unmerged value is at the head of one of the k lists, because each list is sorted. The simplest method scans all k heads for the smallest, takes it, and repeats. That costs O(k) per output node, so O(n · k) in total.

    A min-heap finds the smallest of k items in O(log k) instead. Put the head of each non-empty list into the heap. Then repeat: take the smallest node, append its value to the result, and push that node's successor, if there is one, into the heap. The heap never holds more than one node from each list, so it never has more than k entries. Every one of the n output nodes costs one removal and at most one insertion, each O(log k), which gives O(n log k).

    Step by step

    1. Write a comparator. The lambda cmp takes two ListNode* values and returns a->val > b->val. std::priority_queue is a max-heap by default: its top() is the element that is "largest" under the comparator. Reversing the comparison makes the smallest value come out on top.
    2. Declare the heap. Its type is priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)>, constructed with cmp. Naming a custom comparator needs all three template arguments: the element type, the underlying container, and the comparator type.
    3. Loop over the lists with a range-based for.
    4. Seed the heap. Push each head that is not null. Empty lists contribute nothing.
    5. Create a dummy node. It holds the place before the first real node, so appending the first value needs no special case. The merged list is dummy->next.
    6. Create a tail pointer that always points at the last node appended.
    7. Loop while the heap isn't empty. Each iteration produces one output node.
    8. Take the smallest. Read it with top(), then remove it with pop(). Two calls are needed because pop() returns nothing.
    9. Append a new node with the same value as tail->next.
    10. Feed the heap. If the removed node has a successor, push it. That keeps one candidate from each unfinished list in the heap.
    11. Advance the tail to the node just added.
    12. Return dummy->next, the head of the merged list.

    The solution in C++

    class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minNodes(cmp);
        for (auto* head : lists) {
            if (head) {
                minNodes.push(head);
            }
        }
        ListNode* dummy = new ListNode();
        ListNode* tail = dummy;
        while (!minNodes.empty()) {
            ListNode* minNode = minNodes.top();
            minNodes.pop();
            tail->next = new ListNode(minNode->val);
            if (minNode->next) {
                minNodes.push(minNode->next);
            }
            tail = tail->next;
        }
        return dummy->next;
    }
};

    The C++ details worth knowing:

    • The heap stores pointers, not values. The comparator receives two pointers and looks inside them. Without the custom comparator, the queue would order the pointers by memory address, which says nothing about the values.
    • Comparator direction. The usual mistake is to write a->val < b->val. That gives the default max-heap behaviour and merges in descending order.
    • decltype(cmp). A lambda has a unique compiler-generated type that can't be written by hand. decltype names it, and the object cmp is passed to the constructor so that the queue has a copy to use.
    • auto* head. The element type is ListNode*, so auto* deduces ListNode and keeps the pointer visible. The loop copies each pointer, which is cheap.
    • Testing a pointer. if (head) is true for a non-null pointer, so it filters out empty lists. minNode->next works the same way.
    • New nodes are allocated. The result is built from copies of the values, so the input lists are left untouched. That costs O(n) memory for the output. The statement's O(k) counts the working space of the algorithm, the heap. The dummy node is also never freed. In production code, reuse the input nodes by relinking them, and free or avoid the dummy.

    Complexity

    Time: O(n log k). The heap never holds more than k nodes, so each push and each pop costs O(log k). Each of the n nodes is pushed once and popped once.

    Space: O(k) beyond the output. The heap stores at most one node pointer per list. The merged list itself takes O(n).

    Edge cases and common mistakes

    • No lists. With lists = [], the heap stays empty, the loop doesn't run, and dummy->next is nullptr: the empty list.
    • Only empty lists. [[]], a vector holding one null pointer, gives the same empty result.
    • Pushing null heads. The comparator would dereference a null pointer, which crashes the program. That is why the seeding loop checks if (head).
    • Duplicates and negatives. Equal values are fine, since the comparator uses strict >, and negative values compare like any other integers.
    • Using top() after pop(). Read the node first. After pop() the heap's top is already the next node.
    • Forgetting to push the successor. The result would end after the first node of each list.
    • Returning dummy. That includes the placeholder node, which has value 0, at the front of the answer.

    Testing

    • [[1,4,5],[1,3,4],[2,6]] gives 1->1->2->3->4->4->5->6.
    • [] gives an empty list.
    • [[]] gives an empty list.
    • [[], [-3, -3]] gives -3->-3.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free