解題說明
Remove Nth Node From End of List
題目描述:刪除鏈結串列中倒數第 n 個節點,回傳鏈結串列頭節點。
解題思路:雙指標一次遍歷:讓 fast 指標先走 n 步,然後 fast 和 slow 同時前進。當 fast 到達末尾時,slow 正好在倒數第 n+1 個節點(即目標節點的前驅),執行刪除操作。使用虛擬頭節點處理刪除頭節點的邊界情況。
C++ 解法
複雜度分析
時間複雜度:O(L) — 一次遍歷,L 為串列長度。
空間複雜度:O(1) — 只用兩個指標。
虛擬碼
1. Create dummy node before head 2. fast = slow = dummy 3. Advance fast by (n+1) steps 4. While fast != null: advance both fast and slow 5. slow.next = slow.next.next (delete target) 6. Return dummy.next
其他解法
兩次掃描 O(n) 時間,O(1) 空間:先掃描找長度,再掃描找目標 — 時間複雜度 O(2n),空間優化。
遞迴 O(n) 時間,O(n) 空間:遞迴到末尾,回程時計數並移除 — 空間複雜度更差。
延伸思考
- 若 n 大於列表長度怎辦?
- 如何原地移除(單次掃描)?
- 若移除 m 個節點呢?