23 Merge k Sorted Lists

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

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        priority_queue<pair<int, ListNode*>> heads;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( lists[i] != 0 ) heads.push(pair<int, ListNode*>(-lists[i]->val, lists[i]));
        }
        ListNode* dummy = new ListNode(0);
        ListNode* p = dummy;
        while ( ! heads.empty() ) {
            ListNode* next = heads.top().second;
            heads.pop();
            if ( next->next != NULL ) heads.push(pair<int, ListNode*>(-next->next->val, next->next));
            p->next = next;
            p = next;
        }
        return dummy->next;
    }
};