題目描述:合併 k 個已排序的鏈結串列,回傳一個合併後的已排序串列。
解題思路:使用最小堆(min-heap):將所有串列的頭節點放入堆中。每次彈出最小節點接到結果,並將該節點的下一個節點推入堆中。這樣每次操作 O(log k),總共 O(nk log k)。另一種方法是分治合併:兩兩合併串列,log k 輪,總時間相同。
時間複雜度:O(N log k),N 為所有節點總數,k 為串列數 — 每個節點進出堆各一次。
空間複雜度:O(k) — 堆中最多存 k 個節點。
1. Push all non-null list heads into min-heap 2. Create dummy node, curr = dummy 3. While heap non-empty: a. Pop minimum node b. Attach to curr, advance curr c. If node.next exists: push node.next into heap 4. Return dummy.next
成對合併 O(nk log k):遞迴將 k 個串列分成兩組,分別合併後再合併結果 — 分治方法。
逐一合併 O(nk²):依次合併每個串列至結果 — 簡單但低效。