Merge K Sorted Lists Using Min Heap in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging 3 sorted lists using min heap

What is the printed merged list after running the following C++ code that merges 3 sorted linked lists using a min heap?

DSA C++

#include <iostream>
#include <vector>
#include <queue>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, compare> minHeap;
    for (auto node : lists) {
        if (node) minHeap.push(node);
    }
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!minHeap.empty()) {
        ListNode* top = minHeap.top();
        minHeap.pop();
        tail->next = top;
        tail = tail->next;
        if (top->next) minHeap.push(top->next);
    }
    return dummy.next;
}

int main() {
    ListNode a1(1), a2(4), a3(5);
    a1.next = &a2; a2.next = &a3;
    ListNode b1(1), b2(3), b3(4);
    b1.next = &b2; b2.next = &b3;
    ListNode c1(2), c2(6);
    c1.next = &c2;
    std::vector<ListNode*> lists = {&a1, &b1, &c1};
    ListNode* merged = mergeKLists(lists);
    while (merged) {
        std::cout << merged->val << " -> ";
        merged = merged->next;
    }
    std::cout << "null" << std::endl;
    return 0;
}

A 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

B 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

C 1 -> 1 -> 3 -> 4 -> 5 -> 6 -> null

D 1 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

💡 Hint

Trace the min heap operations and how nodes are popped and pushed.

The min heap always pops the smallest current node among all lists. The merged list contains all nodes in sorted order including duplicates.

🧠 Conceptual

intermediate

Time complexity of merging K sorted lists using min heap

What is the time complexity of merging K sorted lists with a total of N elements using a min heap?

A O(K log N)

B O(N log K)

C O(N K)

D O(N log N)

💡 Hint

Consider how many times elements are pushed and popped from the heap and the heap size.

Each of the N elements is pushed and popped once from a heap of size at most K, so each heap operation costs O(log K). Total is O(N log K).

🔧 Debug

advanced

Identify the runtime error in min heap merge code

What runtime error will occur when running this code snippet that merges K sorted lists using a min heap?

DSA C++

#include <queue>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val < b->val; // Note: reversed comparison
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, compare> minHeap;
    for (auto node : lists) {
        if (node) minHeap.push(node);
    }
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!minHeap.empty()) {
        ListNode* top = minHeap.top();
        minHeap.pop();
        tail->next = top;
        tail = tail->next;
        if (top->next) minHeap.push(top->next);
    }
    return dummy.next;
}

A The merged list will be sorted in descending order, not ascending

B Compilation error due to wrong comparator syntax

C Infinite loop because minHeap never empties

D Segmentation fault due to null pointer dereference

💡 Hint

Check the comparator logic and how it affects the priority queue ordering.

The comparator returns true if a->val < b->val, which makes the priority queue behave like a max heap, so the smallest element is not popped first, resulting in descending order merged list.

📝 Syntax

advanced

Identify the syntax error in min heap comparator

Which option contains the correct syntax for a comparator struct to use in a C++ priority_queue for merging K sorted lists?

A struct compare { bool operator()(ListNode a, ListNode b) { return a.val > b.val; } };

B struct compare { bool operator(ListNode* a, ListNode* b) { return a->val > b->val; } };

C struct compare { bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; } };

D struct compare { bool operator[](ListNode* a, ListNode* b) { return a->val > b->val; } };

💡 Hint

Look for the correct operator overloading syntax for function call operator.

The comparator must overload operator() with pointer parameters. Option C is correct syntax. B misses parentheses after operator, C uses objects not pointers, D uses operator[] which is invalid here.

🚀 Application

expert

Number of nodes in merged list after merging K sorted lists

Given 4 sorted linked lists with lengths 3, 5, 2, and 4 respectively, how many nodes will the merged linked list contain after merging all using a min heap?

A 9

B 12

C 10

D 14

💡 Hint

Sum the lengths of all input lists.

The merged list contains all nodes from all lists, so total nodes = 3 + 5 + 2 + 4 = 14.