class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        for(auto &item : lists){
            if(item) pq.push(item);
        }
        ListNode *head = new ListNode, *temp = head;
        while(!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            temp -> next = top;
            top = top -> next;
            temp = temp -> next;
            if(top) pq.push(top);
        }
        auto ret = head -> next;
        delete head;
        return ret;
    }
    
    struct Compare {
        bool operator()(ListNode *l1, ListNode *l2) {
            return l1 -> val > l2->val;
        }
    };
};