題目

題目翻譯

將 k 個已經排好順序的 linked list 合併成為一個排好序的 list

解題步驟

1. 初始化最小堆（優先隊列）：

   • 優先隊列可以幫助我們每次都找到當前最小的節點，這有助於合併 k 個已經排序的鏈表。
   • 我們遍歷每個鏈表的節點，將每個節點的值存入優先隊列。由於優先隊列會自動將元素進行排序，保證每次取出的元素是當前最小的。

2. 構建結果鏈表：

   • 我們創建一個虛擬的頭節點，這個頭節點的值可以任意，主要用來方便操作。
   • 然後，不斷從優先隊列中取出當前最小的元素，創建一個新節點，並將這個新節點加入結果鏈表。

3. 返回結果：

   • 當優先隊列中的所有元素都處理完後，返回結果鏈表的下一個節點（即跳過虛擬的頭節點）。

code

改寫後的程式碼將進一步優化，以更高效地處理每個節點。

/**
 * 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) {
        // 定義一個最小堆來存放鏈表節點
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        
        // 將所有鏈表的首節點放入最小堆中
        for (ListNode* list : lists) {
            if (list != nullptr) {
                pq.push(list);
            }
        }

        // 使用虛擬頭節點來簡化鏈表操作
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;

        // 當最小堆不為空時，依次取出最小節點，並將其下一個節點加入堆中
        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            cur->next = node;
            cur = cur->next;

            // 如果當前節點有下一個節點，將其加入堆中
            if (node->next) {
                pq.push(node->next);
            }
        }

        // 返回合併後的鏈表，跳過虛擬頭節點
        return dummy->next;
    }
};