LeetCode Merge k Sorted Lists：分治合併 k 個有序鏈表

問題描述

合併 k 個已排序鏈表為一個有序鏈表。分析時間空間複雜度。

分治法（自底向上）

兩兩合併，類似歸併排序：
1. 將 k 個鏈表兩兩配對合併 → k/2 個鏈表
2. 重複直到剩 1 個鏈表

完整代碼

class Solution {
    ListNode* mergeTwo(ListNode* a, ListNode* b) {
        ListNode dummy(0), *tail = &dummy;
        while (a && b) {
            if (a->val < b->val) { tail->next = a; a = a->next; }
            else { tail->next = b; b = b->next; }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }
public:
    ListNode* mergeKLists(vector& lists) {
        if (lists.empty()) return nullptr;
        while (lists.size() > 1) {
            vector next;
            for (size_t i=0; i

複雜度分析

設總節點數 N，每層合併處理所有節點一次 → O(N)
層數 log k → 總時間 O(N log k)
空間：遞歸棧/臨時數組 O(k) → O(k)


優先隊列法（堆）對比
維護大小 k 的小頂堆，每次取最小節點輸出，將其下一節點入堆。時間同 O(N log k)，空間 O(k)。代碼略長但單趟掃描，無需多輪合併。

LeetCode 實測
分治法 144ms (130 測試用例)，堆法約 120ms。兩者均可接受，分治法代碼更簡潔，無需自定義比較器。

關鍵點

歸併兩鏈表是核心子程序，虛擬頭節點簡化邊界處理
分治將 k 路歸併轉化為 log k 輪兩路歸併
空數組、單鏈表、空鏈表等邊界情況需處理


此題是「多路歸併」的經典應用，分治與堆是兩大主流解法，掌握其中任一即可應對面試與工程需求。