23

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */



class Solution {
public:

    struct compare {
        bool operator()(const ListNode* l, const ListNode* r) {
            return l->val > r->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode *, vector<ListNode *>, compare> pq;
        ListNode *dummy = new ListNode(0);
        for(auto head:lists) if(head) pq.push(head);

        ListNode* curr = dummy;
        while(!pq.empty()){
            ListNode *tmp = pq.top();
            curr->next = tmp;
            pq.pop();
            if(tmp->next) pq.push(tmp->next);
            curr = curr->next;
        }
        return dummy->next;
    }
};