Merge Lists合併串列
合併兩條有序串列，K 條時用堆積。
用在：合併排序的核心、合併多個有序資料流
01為什麼需要它
每台伺服器的 log 各自依時間排好，要合成一份總的時間序。把全部倒進陣列再排序是 O(N log N)，而且要先讀進記憶體。
為什麼用它每條都有序，只要反覆比較各條的「目前最前面那筆」、取最小的。兩條是 O(n + m)，k 條用堆積是 O(N log k)，而且可以串流處理。這是外部排序與 log 聚合系統的核心。
合併排序把資料切成兩半各自排好，最後要「把兩段有序的合成一段」。在串列上做這件事不用額外空間。
為什麼用它串列的合併只改指標、不搬資料，所以串列版合併排序是 O(n log n) 時間、O(log n) 空間，比陣列版省。LeetCode 148 Sort List 就是這題。
兩張表都依 join key 排好序，要找出 key 相同的配對。
為什麼用它同樣是雙指標同時往前走：誰小誰前進，相等就輸出。和合併串列是同一個骨架，只是「輸出」的動作不同。
看到這些關鍵字就想到它：兩條（或 k 條）已排序、合併、取最小的那個、合併排序、dummy + tail、多路歸併。
02核心概念
兩條已排序的串列要合成一條有序的，只需要一個觀察：整體最小的一定是兩條的頭之一。取走比較小的那個頭，剩下的仍然是兩條有序串列，重複同樣的事。這就是合併（merge）。每個節點只被比較一次、接上一次，O(n + m)。
寫法上用 dummy 節點當結果的起點、tail 指向結果的最後一個節點。每一輪把較小的頭接到 tail.next、tail 前進、那條串列的頭也前進。其中一條用完時，另一條剩下的部分本來就是接好的，直接把 tail.next 指過去，不用再一個一個接。不建新節點，只改指標，額外空間 O(1)。
合併 k 條時，每輪要在 k 個頭裡挑最小的。用最小堆積維護這 k 個頭，取出最小 O(log k)、把它的下一個放回去 O(log k)，總共 O(N log k)。另一種寫法是兩兩合併、像錦標賽一樣分治，複雜度相同。
反過來，把合併當作零件就得到串列版合併排序：快慢指標找中點切半，遞迴排好兩半，再合併。這是串列排序的標準解，也把前面三篇（快慢指標、遞迴、合併）串在一起。
03演算法步驟
- 1建
dummy，tail = dummy。dummy 讓第一個節點的接法和後面的一樣。 - 2
while a and b：比較a.val和b.val，把較小的接到tail.next，那條串列的指標前進，tail = tail.next。相等時取 a，結果才是穩定的。 - 3迴圈結束後
tail.next = a or b，把還沒用完的那條整段接上。 - 4回傳
dummy.next，不是 dummy。 - 5k 條時把每條的頭放進最小堆積（Python 要加索引當 tie-breaker），每次 pop 最小的接上，再 push 它的 next。
04互動示範
逐步看兩條串列怎麼合併：每一步比較兩個頭，較小的接到結果尾端；一條用完後，另一條剩下的整段直接接上。
05程式碼
迭代版與遞迴版合併兩條、用堆積合併 k 條、以及把合併當零件的串列版合併排序。
import heapq
# 合併兩條有序串列：dummy + tail，每次接上比較小的那個。O(n + m)
def merge_two(a, b):
dummy = tail = ListNode(0)
while a and b:
if a.val <= b.val: # 相等時取 a，保持穩定
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b # 剩下的那段直接接上
return dummy.next
# 遞迴版：merge(a, b) = 較小的那個節點 + merge(剩下的)
def merge_two_rec(a, b):
if not a: return b
if not b: return a
if a.val <= b.val:
a.next = merge_two_rec(a.next, b)
return a
b.next = merge_two_rec(a, b.next)
return b
# 合併 k 條：最小堆積存每條的頭，每次取最小的。O(N log k)
def merge_k(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i 避免比較 node
dummy = tail = ListNode(0)
while heap:
_, i, node = heapq.heappop(heap)
tail.next = tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# 串列版合併排序：快慢指標切半，遞迴排兩半，再合併。O(n log n)、O(log n) 堆疊
def sort_list(head):
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
right, slow.next = slow.next, None # 從中間切開
return merge_two(sort_list(head), sort_list(right))06練習題
- LeetCode 21Merge Two Sorted ListsEasy
- LeetCode 88Merge Sorted Array（陣列版，從後面往前填）Easy
- LeetCode 148Sort List（串列版合併排序）Medium
- LeetCode 23Merge k Sorted Lists（堆積）Hard
- LeetCode 2Add Two Numbers（雙指標同時走的變形）Medium