21. Merge Two Sorted Lists
給兩個已排序的鏈結串列，合併成一個仍然排序的串列。要求接原本的節點，不是建新的。
思路
這就是合併排序（merge sort）最後那一步單獨拿出來考。兩個串列都已排序，所以只要比較兩顆頭，把小的那顆接到結果後面，然後那一邊往前走一步。重複到其中一邊走完為止。
真正的難點不在演算法，在寫起來很容易被邊界搞爛：
- 結果串列的「第一顆」要特別處理嗎？
- 其中一邊先走完了怎麼辦？
- 有一邊一開始就是空的怎麼辦？
第一個問題的標準解法是 dummy head（哨兵節點）：先造一顆假的頭節點，所有接續動作都變成「接在某個已存在的節點後面」，完全不需要為第一顆寫特例。最後回傳 dummy.next 就是真正的頭。
這個手法在鏈結串列題幾乎是無腦必用的，見 Linked List 模板。
第二、三個問題其實是同一件事：跳出迴圈時，最多只有一邊還有剩，而且它本身已經排序好了 —— 所以不需要逐顆搬，直接把整條接上去就行。
解題方向
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
h1 = list1
h2 = list2
res = ListNode(-1)
tmp = res
while h1 != None and h2 != None:
if h1.val < h2.val:
res.next = h1
h1 = h1.next
res = res.next
else:
res.next = h2
h2 = h2.next
res = res.next
while h1 != None:
res.next = h1
h1 = h1.next
res = res.next
while h2 != None:
res.next = h2
h2 = h2.next
res = res.next
return tmp.next
這裡 res 是一路往前移動的游標，tmp 是那顆固定不動的 dummy head。（名字容易看反 —— 大多數人會把 dummy 叫 dummy、游標叫 cur，寫的時候留意一下自己的命名，面試時解釋起來比較順。）
後面那兩個 while 可以縮成一行。 跳出主迴圈時最多只有一邊還有剩，而且它已經排序好了，鏈結串列不需要逐顆搬 —— 直接把整條接上去：
res.next = h1 if h1 else h2
或者更 Python 一點：res.next = h1 or h2。這是鏈結串列比陣列漂亮的地方：陣列合併時剩下的元素得一個個複製，串列只要改一個指標。
補充
< 還是 <=？ 兩邊值相同時，h1.val < h2.val 會走 else 分支先接 h2。答案一樣正確，但這樣不是穩定的（相同值時來自 list2 的排在前面）。這題不在意，不過如果面試官問「合併排序要穩定的話呢」，答案就是把條件改成 <=。
合併家族：
| 題目 | 資料結構 | 合併幾條 | 核心工具 |
|---|---|---|---|
| 21 這題 | 鏈結串列 | 2 | dummy head + 兩指針 |
| 23. Merge k Sorted Lists | 鏈結串列 | k | heap 或兩兩分治 |
| 88. Merge Sorted Array | 陣列（原地） | 2 | 從後往前填 |
這組對照最值得記的是「為什麼只有 88 要反過來」：串列合併只改指標，寫入不破壞資料；陣列原地合併從前面寫會蓋掉還沒讀的元素。資料結構決定了方向。
23 則是把這題當子程序用 —— 兩兩分治那個解法裡的 mergeTwoLists 就是本題。148. Sort List 也一樣（合併排序的完整版，這題是它的合併步驟）。
複雜度
- 時間 — 兩條串列的每個節點都只被走過一次
- 空間 — 只有幾個指標；接的是原本的節點，沒有建新節點（dummy head 那一顆是常數）
其中 m、n 是兩條串列的長度。