題幹與適用場景
給定陣列 lists，其中保存 k 個單向鏈結串列的首節點。請把全部節點合併成一個依非遞減 順序排列的鏈結串列。任一輸入串列都可能為空，數值可以是負數或重複值，所有輸入節點總數記為 N。
假設每個輸入鏈結串列無環、已經有序，且不同輸入不共用節點。實作可以重新連接現有節點，不能 為每個數值都建立替代節點。不同輸入串列中的相等值不要求保持特定順序。陣列為空或所有首節點 都是 None 時回傳 None。目標時間為 O(N log k)，輔助空間為 O(k)。
Input:
1 -> 4 -> 5
1 -> 3 -> 4
2 -> 6
Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6這是一道鏈結串列題，因此指標所有權也是契約的一部分。如果呼叫端要求輸入串列保持不變， 演算法選擇可以不變，但輸出必須建立 N 個新節點，輸出空間會變為 O(N)。
面試官考察點
第一項訊號是能否利用輸入已有序。把全部值攤平後排序可以得到正確結果，但需要 O(N log N) 時間與 O(N) 額外儲存。每輸出一個節點就掃描全部目前首節點，雖然利用了有序性，仍需 O(Nk)。強回答會先問：下一個全域最小值可能位於哪個小集合？
第二項訊號是候選首節點不變量。對每條未耗盡串列，只有第一個尚未合併的節點可能成為下一個 輸出；因為串列有序，它後面的每個節點都不小於這個首節點。因此，最小堆積只需保存每條未耗盡 串列的一個候選首節點，就能把最多 k 個候選的線性掃描變成大小不超過 k 的堆積刪除與插入。
第三項訊號是證明與複雜度核算。回答應說明：選出的節點為何是全域最小值、為何只壓入它的後繼 就能恢復不變量、為何每個節點恰好輸出一次，以及堆積為何不會超過非空串列數。只說「用優先 佇列」沒有展示核心推導。
第四項訊號是實作細節。在 Python 中，如果兩個堆積項目的數值優先級相同，tuple 比較不能 繼續比較 ListNode 物件。加入唯一序號可以消除這個問題。重用節點時，程式先保存原後繼，再 斷開並附加目前節點，使已建構前綴只有一個明確所有者，不會暫時指向尚未合併的串列。
最後一項訊號是能否在兩種最佳方案間做選擇。最小堆積與平衡兩兩合併都能達到 O(N log k)。 最小堆積把候選集合寫得更明確，也容易延伸到迭代器或串流；分治只使用一般的雙串列合併，在 保存首節點的陣列之外可以只用常數級指標空間。應依輸入契約選擇較容易解釋的方案。
回答前需要釐清的問題
- 可以修改並重用輸入節點嗎？ 可以就重新連線，只保留
O(k)堆積狀態；不可以就建立輸出
節點，並把 O(N) 輸出空間與演算法輔助狀態分開回報。
- 所有輸入都保證有序且無環嗎？ 基礎演算法依賴這兩點。驗證有序性需要
O(N)，偵測環也
會增加工作，不能預設塞進基礎解法。
k具體計算什麼？ 令m為非空串列數。堆積最多保存m個元素，因此m >= 2時
更精確的界是 O(N log m)，零或一條非空串列時為線性。
- 相等值是否要保持跨串列順序？ 基礎題只要求數值有序。穩定性契約必須先定義來源順序，
再把它編碼進堆積鍵。
- 可以使用語言標準函式庫的優先佇列嗎？ 除非面試官還要另外考察堆積實作，通常可以。應先
確認，不要直接花面試時間手寫二元堆積。
- 輸入是完整鏈結串列還是惰性迭代器？ 最小堆積都能處理，但迭代器版本只能在目前值被取出
後推進對應來源。
- 輸入首節點陣列應保持什麼狀態？ 下方程式不會修改陣列項目，但會重新連接其中的節點。
如果呼叫端同時觀察兩者，應明確這是所有權轉移。
30 秒回答框架
「每條有序鏈結串列只有第一個未合併節點可能成為下一個全域最小值，所以我會把這些候選首節點 放入最小堆積。每次彈出最小節點並附加到結果，再只壓入它保存下來的後繼。不變量是：堆積恰好 包含每條未耗盡串列的一個候選首節點；因此彈出的節點一定安全，補上其來源的後繼又恢復不變量。 N 個節點各彈出一次，最多各壓入一次，堆積大小不超過 k，所以時間是 O(N log k)，輔助 空間是 O(k)。實作會重用節點，加入唯一序號避免相等值觸發節點物件比較，並測試空輸入、重複 值、負數、長度差異與單串列。主要替代方案是同複雜度的平衡兩兩合併。」
分步深入解答
先列出直接方案，找到重複工作：
| 方案 | 時間 | 輔助空間 | 重複或捨棄的資訊 | |---|---:|---:|---| | 攤平數值、排序、重建 | O(N log N) | O(N) | 捨棄每個輸入已經有序的條件 | | 每個節點掃描最多 k 個首節點 | O(Nk) | O(1) | 重複執行 N 次線性最小值尋找 | | 逐條合併進累積結果 | 最壞 O(Nk) | O(1) | 早期節點在後續合併中反覆走訪 | | 平衡兩兩合併 | O(N log k) | O(1) 指標空間 | 每一層合併處理全部節點一次 | | 候選首節點最小堆積 | O(N log k) | O(k) | 透過堆積操作選擇下一個來源 |
依序合併的成本容易被低估。假設 k 條串列長度接近 L，工作量依 2L + 3L + ... + kL 成長，即 O(Lk²)。因為 N = Lk，所以最壞為 O(Nk)。兩兩合併 透過分輪保持平衡，每個節點最多參加 ceil(log₂ k) 層合併，避免不斷成長的累積結果。
對最小堆積方案，在每次刪除堆頂前維持下列不變量：
For each non-exhausted input list:
the heap contains exactly its first unmerged node.
For each exhausted input list:
the heap contains no node from that list.
The result contains every previously removed node exactly once,
in non-decreasing order.初始化把每個非空首節點壓入堆積，因此不變量成立。假設某輪開始時不變量成立。任何未合併節點 要麼是堆積中的候選首節點，要麼位於某個候選首節點之後。因為每條輸入有序，更深的節點不可能 小於該候選首節點。所以堆積中最小項目不大於任何未合併節點，可以安全附加。
取出節點後，只有它所屬串列失去代表。先保存該節點的原後繼，斷開並附加該節點；如果後繼存在， 就把後繼壓入堆積。其他來源的候選首節點保持有效，不變量恢復。每輪輸出一個節點，恰好 N 輪 後所有串列耗盡、堆積為空，由此證明結果有序、節點完整且演算法終止。
下方 Python 實作把單調遞增序號放在 tuple 第二項。序號唯一，所以數值相等時，tuple 比較不會 繼續到不可排序的節點物件。
from __future__ import annotations
from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count
@dataclass
class ListNode:
val: int
next: ListNode | None = None
def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
heap: list[tuple[int, int, ListNode]] = []
sequence = count()
for head in lists:
if head is not None:
heappush(heap, (head.val, next(sequence), head))
dummy = ListNode(0)
tail = dummy
while heap:
_, _, node = heappop(heap)
next_node = node.next
node.next = None
tail.next = node
tail = node
if next_node is not None:
heappush(heap, (next_node.val, next(sequence), next_node))
return dummy.next初始有 m 次插入，其中 m <= k 是非空串列數。每個節點刪除一次，除各串列尾節點外，每個 節點還可能引發一次後繼插入。堆積最多有 m 個項目，操作成本為 O(log m)。m >= 2 時總 時間為 O(N log m)，通常寫作 O(N log k)；m <= 1 時走訪為 O(N)。堆積、序號計數器、 虛擬節點與指標使用 O(m) 輔助空間。回傳的是原節點，不屬於新增演算法儲存。
斷開 node.next 不會遺失後繼，因為後繼已先保存。如此已合併前綴不會暫時指向尚未贏得堆積 選擇的來源節點，指標所有權更清楚。下一次附加會為尾節點設定新後繼。在無環且各輸入節點互不 共享的契約下，演算法不會修改數值，也不會重複壓入同一個節點。
測試應涵蓋結構，而不只涵蓋一組正常數值：
def build(values: list[int]) -> ListNode | None:
dummy = ListNode(0)
tail = dummy
for value in values:
tail.next = ListNode(value)
tail = tail.next
return dummy.next
def values(head: ListNode | None) -> list[int]:
result: list[int] = []
while head is not None:
result.append(head.val)
head = head.next
return result
cases = [
([], []),
([[]], []),
([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
([[], [-3, -1, 2], [], [-3, 7]], [-3, -3, -1, 2, 7]),
([[5]], [5]),
]
for raw_lists, expected in cases:
actual = values(merge_k_lists([build(items) for items in raw_lists]))
assert actual == expected, (raw_lists, expected, actual)正式環境驗證還應記錄所有輸入節點的身分，用 visited 集合走訪輸出，並證明三件事：沒有環、 恰好有 N 個不同節點身分、相鄰數值非遞減。這能找出只比較數值時可能遺漏的重複插入、節點 遺失與指標環。
當面試官重點考察指標操作、沒有優先佇列，或希望減少堆積儲存時，選擇平衡兩兩合併。當來源以 迭代器形式提供、活躍來源數會變化，或明確展示「下一個全域候選」的機制更易理解時，選擇最小 堆積。在基礎契約下兩者都是正確的最佳回答，關鍵是說明選擇理由。
高品質示範回答
「我會重用輸入節點，並假設每條鏈結串列有序、無環且互不共享。令 N 為總節點數、m 為 非空串列數。下一個輸出只可能是 m 個目前首節點之一，因為更深的節點不小於所在串列的首節點。 因此我會把每條非空串列的一個首節點放進最小堆積。
不變量是：堆積恰好包含每條未耗盡串列的第一個未合併節點，輸出包含所有已彈出節點且保持有序。 每次刪除最小項目，保存並斷開它的後繼，附加目前節點，再壓入後繼。彈出節點一定安全，因為其他 任何未合併節點都位於某個不大於它的堆積候選之後；補入後繼又恢復每條串列一個候選的不變量。
Python 堆積項目寫成 (value, sequence, node)。唯一序號避免相等優先級繼續比較節點物件； 題幹沒有要求跨串列穩定順序，所以不額外聲稱穩定性。每個節點彈出一次、最多壓入一次，堆積最多 有 m 項，因此時間是 O(N log m)，通常寫作 O(N log k)，輔助空間是 O(m)；零或一條 非空串列時為線性。
我會測試空陣列、全部為空、單串列、長度差異、負數與相等值。因為解法重新連接指標，還會驗證 節點身分與無環。平衡兩兩合併是主要替代方案，同樣是 O(N log k)，只使用雙串列合併原語； 如果題目重點是指標實作或禁止標準函式庫堆積，我會選擇它。」
常見錯誤
- 直接攤平並排序 → 忽略輸入已有序，花費
O(N log N)與輸出儲存 → **維護每個有序來源
的一個候選首節點。**
- 每個節點都掃描
k個首節點 → 最小值選擇變成O(Nk)→ **使用大小不超過k的最小
堆積或平衡兩兩合併。**
- 依序合併進不斷成長的結果 → 早期節點在之後多次被走訪 → 按輪次平衡合併。
- 把所有節點都壓入堆積 → 堆積增至
N，工作退化為O(N log N)→ **每個來源只壓入
一個目前節點。**
- Python 堆積保存
(value, node)→ 相等值會比較不可排序的節點物件 → **加入唯一數值
序號。**
- 保存後繼之前就推進或改線 → 可能遺失剩餘串列 → 先保存後繼，再斷開並附加。
- 因為重用節點就聲稱
O(1)空間 → 堆積仍保存最多k個項目 → **分開核算輸出配置與
輔助狀態。**
- 只驗證輸出數值 → 環、重複節點或節點遺失可能未被發現 → **檢查節點身分、數量、有序性
與無環。**
- 沒有確認就加入排序與環偵測 → 實作擴大了契約並改變成本 → **先聲明假設，只在要求時增加
驗證。**
追問與應對
為什麼堆頂就是下一個全域最小值？
每條未耗盡有序串列提供第一個未合併節點。其他節點都位於某個候選首節點之後，不可能小於這個 候選首節點。因此，最小候選首節點不大於任何未合併節點。彈出它是安全的，壓入它的後繼就恢復 該來源的涵蓋。
如果相等值必須依輸入串列順序穩定輸出，怎麼改？
先精確定義穩定性，再把堆積鍵寫成數值加來源串列索引。因為每個來源同時只有一個節點在堆積中， 來源索引解決跨串列相等值，串列內部順序自然保持。基礎實作中的序號只保證可比較性，不保證這項 更強策略。
何時分治優於最小堆積？
已經有雙串列合併、面試重點是指標操作，或不能用優先佇列時，採用平衡兩兩合併。每輪處理一次 全部剩餘節點，共 O(log k) 輪。對惰性來源與活躍來源數變化，最小堆積更直接。
如果輸入鏈結串列必須保持不變呢？
保留相同的候選選擇邏輯，但每彈出一個數值就建立新節點。時間仍為 O(N log k)。候選選擇 狀態仍是 O(k)，必要的輸出配置是 O(N)；兩項應分別說明，不能把輸出空間隱藏掉。
如果有一萬個串列欄位，但只有五條非空呢？
初始化需要掃描一次 k 個欄位，之後堆積最多只有 m = 5 項。精確時間為 O(k + N log m)，輔助空間為 O(m)。只寫 O(N log k) 仍是安全上界，但沒有呈現跳過空 首節點的收益。
如果輸入是有序迭代器而不是鏈結串列呢？
從每個非空迭代器讀取一個值，與來源身分一起放入堆積。產出最小值後只推進該來源並插入下一個 值。候選首節點證明不變，結果可以惰性生成，記憶體與活躍來源數成正比，而不是與總數值數成正比。
彈出節點有後繼時，可以使用 heapreplace 嗎？
如果已經單獨執行 heappop，舊堆頂已經離開，不能再 replace。另一種實作可以先查看堆頂，在 該來源有後繼時一次替換；來源耗盡時仍需單獨分支。面試中先彈出再壓入更容易證明，漸進複雜度 相同。
除了範例，如何測試指標正確性？
合併前保存每個輸入節點身分。走訪結果時拒絕重複身分，確認恰好 N 個節點、每對相鄰值有序， 且身分集合完全相同。再隨機產生有序串列，把結果數值與可信的攤平排序 oracle 比較；oracle 用於 測試，不代表正式解法複雜度。