LeetCode 23 合併 K 個有序鏈表：優先隊列（最小堆）O(N log k) 最優解

題目描述

合併 k 條已排序的鏈表，返回合併後的有序鏈表。分析時間複雜度。

方法一：兩兩合併（超時）

依次將當前結果與下一條鏈表合併，時間 O(k × N)，其中 N 為總節點數。LeetCode 測試用例大時會 TLE。

// TLE 版本
ListNode* mergeKLists(vector<ListNode*> &lists) {
    ListNode *head = nullptr;
    for (auto list : lists) head = mergeTwoLists(head, list);
    return head;
}

方法二：最小優先隊列（最小堆） - AC

核心思想

1. 將 k 條鏈表的頭節點放入最小堆
2. 每次取出堆頂最小節點，接入結果鏈表
3. 若該節點有 next，將 next 入堆
4. 堆空時結束

堆中始終維護 k 個候選最小節點，每次操作 O(log k)，總節點 N，總體 O(N log k)。

AC 代碼

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct ListNode {
    int val; ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*> &lists) {
        ListNode dummy(-1);
        ListNode *tail = &dummy;
        
        // 自定義比較器：最小堆
        struct Compare {
            bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; }
        };
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        
        // 初始化：非空鏈表頭節點入堆
        for (auto node : lists) if (node) pq.push(node);
        
        while (!pq.empty()) {
            ListNode *cur = pq.top(); pq.pop();
            tail->next = cur;
            tail = cur;
            if (cur->next) pq.push(cur->next);
        }
        return dummy.next;
    }
};

// 輔助：構建鏈表、輸出、主函數測試（略）

複雜度分析

關鍵點

• 使用 dummy 節點簡化頭節點處理
• 自定義 Compare 實現最小堆（默認 priority_queue 為最大堆）
• 僅將非空節點入堆，避免空指針
• 每個節點進出堆各一次，共 2N 次堆操作

運行結果截圖