023.md

23. Merge k Sorted Lists

Solution 1

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

struct compare{
    bool operator () (ListNode* a, ListNode* b) {
        if (a->val > b->val)
            return true;
        else
            return false;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, compare> heap;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL)
                heap.push(lists[i]);
        }
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        while (!heap.empty()) {
            ListNode* cur = heap.top();
            heap.pop();
            p->next = cur;
            p = p->next;
            if (cur->next != NULL)
                heap.push(cur->next);
        }
        return dummy->next;
    }
};