題目描述:刪除鏈結串列中倒數第 n 個節點,回傳鏈結串列頭節點。
解題思路:雙指標一次遍歷:讓 fast 指標先走 n 步,然後 fast 和 slow 同時前進。當 fast 到達末尾時,slow 正好在倒數第 n+1 個節點(即目標節點的前驅),執行刪除操作。使用虛擬頭節點處理刪除頭節點的邊界情況。
時間複雜度: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) 空間:遞迴到末尾,回程時計數並移除 — 空間複雜度更差。