Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution: Use min-heap

Note the struct compare and dummy head

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct compare{
        bool operator()(const pair<int, ListNode*> &A, const pair<int, ListNode*> &B){
            return A.first>B.first;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<pair<int, ListNode*>, vector<pair<int, ListNode*>>,compare> pq ;
        for(ListNode* node : lists){
            if(node) pq.push({node->val, node});
        }
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        while(!pq.empty()){
            ListNode* node = pq.top().second; pq.pop();
            cur->next = node;
            cur = cur->next;
            node = node->next;
            if(node) pq.push({node->val, node});
        }
        return head->next;
    }
};