Merge K sorted linked lists.

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

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

// CompareVal function compares the value of the nodes to be inserted into a min heap.
class CompareVal {
    public:
    bool operator() (const Node* a, const Node* b) const {
        if (a->val > b->val)
            return true;
        return false;
    }
};

Node* Merge_Sorted_Linked_Lists ( std :: vector<Node*>& lists) {

    std :: priority_queue <Node*, std :: vector<Node*>, CompareVal> pq_nodes;

    // Push all the nodes in a min heap created from a priority queue.
    for (auto& head : lists) {
        while (head != nullptr) {
            pq_nodes.push(head);
            head = head->next;
        }
    }

    Node * head = nullptr;
    Node * current = nullptr;

    // Pop all the nodes from the min heap (priority queue) and merge into a single list.
    if (!pq_nodes.empty()) {
        head = pq_nodes.top();
        pq_nodes.pop();
        current = head;
        current->next = nullptr;

        while (!pq_nodes.empty()) {
            current->next = pq_nodes.top();
            pq_nodes.pop();
            current = current->next;
        }
        current->next = nullptr; // Set the tail to nullptr;
    }
    return head;
}

void Display_List (Node * head) {
   std :: cout << "List : [ ";
    while (head != nullptr) {
        std :: cout << head->val << " ";
        head = head->next;
    } std :: cout << "]" << std :: endl;
}

int main() {

    // List [ 1, 4, 8 ]
    Node* n1_in_1 = new Node(1);
    Node* n4_in_1 = new Node(4);
    Node* n8_in_1 = new Node(8);

    n1_in_1->next = n4_in_1;
    n4_in_1->next = n8_in_1;

    // List [ 1, 5, 6 ]
    Node* n1_in_2 = new Node(1);
    Node* n5_in_2 = new Node(5);
    Node* n6_in_2 = new Node(6);

    n1_in_2->next = n5_in_2;
    n5_in_2->next = n6_in_2;

    // List [ 1, 4, 5, 6, 7, 8 ]
    Node* n1_in_3 = new Node(1);
    Node* n4_in_3 = new Node(4);
    Node* n5_in_3 = new Node(5);
    Node* n6_in_3 = new Node(6);
    Node* n7_in_3 = new Node(7);
    Node* n8_in_3 = new Node(8);

    n1_in_3->next = n4_in_3;
    n4_in_3->next = n5_in_3;
    n5_in_3->next = n6_in_3;
    n6_in_3->next = n7_in_3;
    n7_in_3->next = n8_in_3;

    std :: vector<Node *> heads = { n1_in_1, n1_in_2, n1_in_3 };

    // Print all the lists before merging.
    for (auto& head : heads) {
        Display_List(head);
    }

    // Merge all the sorted lists.
    Node * head = Merge_Sorted_Linked_Lists(heads);

    // Print the merged list and free the nodes.
    std :: cout << "Merged list in sorted order : [ ";
    while (head != nullptr) {
        std :: cout << head->val << " ";
        Node * tmp = head->next;
        delete head;
        head = tmp;
    } std :: cout << "]";

    return 0;
}

List : [ 1 4 8 ]
List : [ 1 5 6 ]
List : [ 1 4 5 6 7 8 ]
Merged list in sorted order : [ 1 1 1 4 4 5 5 6 6 7 8 8 ]