Merge K Sorted Lists Using Min Heap in DSA C++ - Build from Scratch

Merge K Sorted Lists Using Min Heap

📖 Scenario: You are working on a system that merges multiple sorted data streams into one sorted stream efficiently. This is common in search engines, data processing, and real-time analytics.

🎯 Goal: Build a program that merges k sorted linked lists into one sorted linked list using a min heap (priority queue) for efficient merging.

📋 What You'll Learn

Create k sorted linked lists with given values

Use a min heap (priority queue) to merge these lists efficiently

Output the merged sorted linked list

💡 Why This Matters

🌍 Real World

Merging multiple sorted data streams is common in search engines, log processing, and real-time data analytics where data arrives in sorted chunks.

💼 Career

Understanding how to merge sorted lists efficiently using heaps is important for software engineers working on databases, big data, and systems programming.

1

Create K Sorted Linked Lists

Create three sorted linked lists named list1, list2, and list3 with these exact values: - list1: 1 -> 4 -> 7 -> null - list2: 2 -> 5 -> 8 -> null - list3: 3 -> 6 -> 9 -> null Use the provided ListNode struct and create the lists by linking nodes manually.

DSA C++

#include 

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

int main() {
    // Create list1: 1 -> 4 -> 7 -> null
    // Create list2: 2 -> 5 -> 8 -> null
    // Create list3: 3 -> 6 -> 9 -> null
    // Your code here
    return 0;
}

Hint

Use the new keyword to create nodes and link them using the next pointer.

2

Store Lists in a Vector

Create a std::vector<ListNode*> named lists and add list1, list2, and list3 to it.

DSA C++

#include 
#include 

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

int main() {
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(4);
    list1->next->next = new ListNode(7);

    ListNode* list2 = new ListNode(2);
    list2->next = new ListNode(5);
    list2->next->next = new ListNode(8);

    ListNode* list3 = new ListNode(3);
    list3->next = new ListNode(6);
    list3->next->next = new ListNode(9);

    // Create vector lists and add list1, list2, list3
    // Your code here
    return 0;
}

Hint

Use curly braces {} to initialize the vector with the three list pointers.

3

Merge Lists Using Min Heap

Write a function ListNode* mergeKLists(std::vector<ListNode*>& lists) that merges the k sorted linked lists using a std::priority_queue as a min heap. Use a custom comparator to order nodes by their val. Return the head of the merged sorted linked list.

DSA C++

#include 
#include 
#include 

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

std::vector lists = {};

ListNode* mergeKLists(std::vector& lists) {
    // Implement merge using min heap
    // Your code here
}

int main() {
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(4);
    list1->next->next = new ListNode(7);

    ListNode* list2 = new ListNode(2);
    list2->next = new ListNode(5);
    list2->next->next = new ListNode(8);

    ListNode* list3 = new ListNode(3);
    list3->next = new ListNode(6);
    list3->next->next = new ListNode(9);

    std::vector lists = {list1, list2, list3};

    // Call mergeKLists here
    // Your code here
    return 0;
}

Hint

Use a priority queue with a custom comparator that compares ListNode values to always get the smallest node.

4

Print the Merged Sorted List

Write a while loop to print the merged linked list starting from mergedHead. Print each node's val followed by ->. End with null.

DSA C++

#include 
#include 
#include 

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& lists) {
    std::priority_queue, Compare> minHeap;

    for (auto list : lists) {
        if (list != nullptr) {
            minHeap.push(list);
        }
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (!minHeap.empty()) {
        ListNode* smallest = minHeap.top();
        minHeap.pop();
        tail->next = smallest;
        tail = tail->next;
        if (smallest->next != nullptr) {
            minHeap.push(smallest->next);
        }
    }

    return dummy.next;
}

int main() {
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(4);
    list1->next->next = new ListNode(7);

    ListNode* list2 = new ListNode(2);
    list2->next = new ListNode(5);
    list2->next->next = new ListNode(8);

    ListNode* list3 = new ListNode(3);
    list3->next = new ListNode(6);
    list3->next->next = new ListNode(9);

    std::vector lists = {list1, list2, list3};

    ListNode* mergedHead = mergeKLists(lists);

    // Print merged list
    // Your code here
    return 0;
}

Hint

Use a while loop to traverse the merged list and print each node's value followed by ->. End with null.