23. 合併 K 個升序列表

思路

因為每個鏈表都是有序的，跟合併排序一樣，不過現在有 k 個指針，每次需要找到這些數字中的最小值。
每次找到最小值之後，將對應鏈表的下一個數值加入到參考中，然後再找一次最小值。
這樣就能排序好這些數字了。

問題在於，要怎麼快速找到「一堆數字中的最小值」，並且在加入新數字之後，依舊能快速取出最小值？
每次都排序顯然不現實，對於這種「資料會變動」，但是又有取極端值的需求，通常都會使用堆（優先隊列）
當一個數字加入到堆並維持有序，複雜度是 $O(\log{n})$，取出節點時直接拿第一個是 $O(1)$ 操作，很適合去維護這k個指針指向的數字，以及取出跟插入操作。

程式碼

優先隊列

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { // 定義排序方式
            return a -> val > b -> val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        for(auto node : lists) { 
            if(node != nullptr) { // 把每個鏈表的第一個節點加到 pq 中
                pq.push(node);
            }
        }
        ListNode* dummy = new ListNode(); // 頭節點，方面回傳
        ListNode* tail = dummy; // 當前鏈表的尾端
        while(!pq.empty()) {
            tail -> next = pq.top();
            tail = tail -> next;
            
            ListNode* newNode = pq.top() -> next;
            pq.pop();

            if(newNode != nullptr) {
                pq.push(newNode);
            }
        }
        return dummy -> next;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$