// Merge K Sorted Lists [C++] (LC version 3.06).

#include <queue>
#include <tuple>
#include <iostream>
using namespace std;

// List.

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

ListNode* createList(const vector<int>& v)
{
    ListNode* s = nullptr;
    for (auto i = v.rbegin(), n = v.rend(); i != n; ++i)
        s = new ListNode(*i, s);
    return s;
}

void deleteList(ListNode* s)
{
    while (s) {
        ListNode* next = s->next;
        delete s;
        s = next;
    }
}

void printList(ListNode* first)
{
    cout << '[';
    for (ListNode* s = first; s; s = s->next)
        cout << (s != first ? ", " : "") << s->val;
    cout << "]\n";
}

// Merge.

ListNode* mergeKLists(const vector<ListNode*>& lists)
{
    typedef tuple<int, int, ListNode*> T;
    typedef priority_queue<T, vector<T>, greater<T>> pq_type;

    if (lists.empty())
        return nullptr;

    pq_type q;
    for (int k = 0, n = lists.size(); k < n; k++) {
        ListNode* s = lists[k];
        if (s)
            q.emplace(s->val, k, s);
    }

    if (q.empty())
        return nullptr;

    for (ListNode temp, * t = &temp;;) {
        auto [_, k, s] = q.top();
        q.pop();
        t->next = s;
        if (q.empty())
            return temp.next;
        t = t->next;
        s = s->next;
        if (s)
            q.emplace(s->val, k, s);
    }
}

// Show.

int main()
{
    ListNode* l0 = createList({});
    ListNode* l1 = createList({1, 3, 5, 7});
    ListNode* l2 = createList({2, 4, 6});
    ListNode* l3 = createList({0, 4, 8});

    printList(l0);
    printList(l1);
    printList(l2);
    printList(l3);

    printList(mergeKLists({}));
    printList(mergeKLists({l0}));
    printList(mergeKLists({l1}));
    l0 = mergeKLists({l0, l1, l2, l3});
    printList(l0);

    deleteList(l0);
}