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

Merge k Sorted Lists.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct node {
    int index;
    ListNode* n;
    
    bool operator < (const node& other) const {
        return n->val >= other.n->val;
    }
};
 
 
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(lists.size() == 0) {
            return NULL;
        }
        vector<node> heap;
        ListNode result(-1);
        ListNode* nextNode = &result;
        
        for(int i = 0; i < lists.size(); ++i) {
            ListNode*& cur = lists[i];
            if(cur != NULL) {
                node tmp;
                tmp.n = cur;
                tmp.index = i;
                heap.push_back(tmp);
                cur = cur -> next;
            }
        }
        
        make_heap(heap.begin(), heap.end());
        
        while(!heap.empty()) {
            pop_heap(heap.begin(),heap.end());
            node next = heap.back();
            heap.pop_back();
            
            next.n -> next = NULL;
            nextNode->next = next.n;
            nextNode = nextNode->next;
            
            ListNode*& curList = lists[next.index];
            
            if(curList != NULL) {
                node tmp;
                tmp.n = curList;
                tmp.index = next.index;
                curList = curList->next;
                heap.push_back(tmp);
                push_heap(heap.begin(), heap.end());
            }
        }
        
        return result.next;
        
    }
};