LeetCode - 23 解題紀錄

題目： LeetCode - 23. Merge k Sorted Lists

題目說明

給 k 個已經由小到大排序好的 Lists，將全部合成一個由小到大排序的 List。

解題思路

使用 priority_queue 幫我們排序，由於是自定義的型態，所以需要自己寫比較函數。先遍歷一次 lists 將所有 list 的 head 都推入，接著將 pq.top() 連接，若 pq.top()->next 存在，就重新推入。

參考解法

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* l, ListNode* r) { return l->val > r->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        auto head = new ListNode(), tail = head;
        for(auto& ptr : lists) if(ptr) pq.push(ptr);
        while(!pq.empty())
        {
            tail->next = pq.top(), tail = tail->next, pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        return head->next;
    }
};