Linked List 經典題
Linked list 的題目變化不多，來來回回就是那幾個技巧。把下面這幾題做熟，大部分 linked list 題目都能拆解出來。
三個核心技巧
1. Dummy head（虛擬頭節點）
在真正的 head 前面接一個假節點，讓「刪除第一個節點」和「刪除中間節點」變成同一段程式碼，不必特別處理邊界。
struct ListNode dummy;
dummy.next = head;
struct ListNode *prev = &dummy;
// ... 操作 ...
return dummy.next; // 注意回傳的是 dummy.next，不是 head
只要題目可能刪掉或換掉 head，就用 dummy head。 這是 linked list 題最高 CP 值的技巧。
2. 快慢指標（fast / slow pointer）
兩個指標同時走，快的一次走兩步、慢的一次走一步。快的走到底時，慢的正好在中點。
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// slow 現在在中點
用途：找中點、找倒數第 k 個（快的先走 k 步）、偵測環（Floyd 判圈法）。
3. 三指標翻轉
翻轉時必須先存好 next，否則指標一改就找不到後面了。
struct ListNode *prev = NULL, *cur = head;
while (cur) {
struct ListNode *next = cur->next; // 先存
cur->next = prev; // 再翻
prev = cur;
cur = next;
}
return prev; // prev 是新的 head
題目
2095. Delete the Middle Node of a Linked List
刪掉正中間的節點（n/2 向下取整，0-indexed）。
技巧：快慢指標找中點，但要多留一個 prev 指向 slow 的前一個，才刪得掉。
坑：只有一個節點時要回傳 NULL，直接進迴圈會出錯，先特判。
82. Remove Duplicates from Sorted List II
已排序的 list，把所有出現超過一次的值整批刪掉（不是留一個，是一個都不留）。
技巧：dummy head + 兩指標。prev 停在確定要保留的節點上，cur 往前探；發現 cur->val == cur->next->val 就一路往前跑到值變了為止，然後 prev->next = cur->next 一次跳過整段。
坑：這題和第 83 題（每個值留一個）容易搞混。83 題不需要 dummy head，因為第一個節點一定留得住；82 題第一個節點可能被刪掉，所以一定要 dummy head。
24. Swap Nodes in Pairs
兩兩交換相鄰節點。
技巧：dummy head + 每次處理一對。交換時要動三條指標，順序不能亂：
prev → a → b → rest
變成
prev → b → a → rest
prev->next = b;
a->next = b->next;
b->next = a;
prev = a; // 下一輪的 prev 是 a，不是 b
坑：迴圈條件是 while (prev->next && prev->next->next) ——剩下奇數個節點時要停下來，最後一個保持不動。
25. Reverse Nodes in k-Group
每 k 個一組做翻轉，不足 k 個的尾巴保持原樣。這題是第 24 題的一般化（k=2 就是第 24 題），也是 linked list 的經典難題。
做法：
- 先往前數 k 步，確認真的有 k 個節點，不夠就直接 return（尾巴不動）。
- 用三指標翻轉這 k 個。
- 把翻轉後的這段接回去：前一段的尾巴接新的頭，這段原本的頭（現在是尾）接下一段。
- 更新
prev到這段的尾巴，遞迴或迴圈處理下一段。
坑：接線的順序最容易出錯。建議在紙上先畫好「翻轉前後各節點的位置」，把每一條要改的指標列出來再寫。
2487. Remove Nodes From Linked List
刪掉所有「右邊存在比它大的值」的節點。等價於：只保留從右往左看的遞減序列。
兩種做法：
- 翻轉法：先整條翻轉，從左往右掃時維護目前的最大值，比最大值小的就刪掉，最後再翻回來。直觀好寫。
- 單調堆疊：用一個遞減的 stack，遇到比 stack 頂端大的值就一路 pop，最後把 stack 裡剩下的串起來。
也可以用遞迴：先處理後面，再決定當前節點要不要留——本質上就是「從右往左」。
23. Merge k Sorted Lists
把 k 條已排序的 list 合併成一條。假設總共 N 個節點。
| 做法 | 時間複雜度 | 說明 |
|---|---|---|
| 逐條合併 | O(kN) | 最直覺但最慢，第 i 條要重掃前面已合併的部分 |
| 最小堆（priority queue） | O(N log k) | 堆裡固定放 k 個候選節點，每次取最小的接上去 |
| 分治兩兩合併 | O(N log k) | 像 merge sort，k 條兩兩合併，做 log k 輪 |
面試通常期待後兩種其中之一。分治法不需要額外資料結構，程式碼也短，但堆的做法在「資料是串流進來」時更自然。
坑：輸入陣列裡可能有 NULL（空 list），放進堆之前要先過濾。
除錯建議
Linked list 的 bug 幾乎都是這三類，出問題先往這裡查：
- 忘記存 next：改了
cur->next之後才發現找不到原本的下一個。 - 回傳錯的 head：用了 dummy head 卻回傳
head而不是dummy.next。 - 迴圈條件邊界：
while (cur)還是while (cur && cur->next)？取決於迴圈裡有沒有存取cur->next->next。存取到哪一層，條件就要檢查到哪一層。
實作細節見 Single Linked list。