解題說明
Swapping Nodes in a Linked List
題目描述:給定一個鏈結串列和整數 k,交換第 k 個節點(從頭數)和第 k 個節點(從尾數)的值,回傳修改後的串列。
解題思路:使用一次遍歷完成。先找到第 k 個節點 front,同時從頭節點出發另一指標 back,讓 front 繼續走到串列末尾,此時 back 正好指向從尾數第 k 個節點。具體步驟:走 k-1 步找到 front,記錄此位置;再讓 front 和 back(初始在 head)同步前進直到 front 到達末尾。最後只需交換 front 和 back 指標所指節點的值即可,無需實際調換節點位置。此技巧是「找倒數第 k 個節點」的經典應用。
C++ 解法
複雜度分析
時間複雜度:O(n) — 整個串列只遍歷一次(或最多兩次常數倍的遍歷)。
空間複雜度:O(1) — 只使用常數個指標,原地交換值。
虛擬碼
1. Move front pointer k-1 steps from head to reach k-th node 2. Save this node as first 3. Set back = head 4. While front.next is not null: a. front = front.next b. back = back.next 5. Swap values of first and back 6. Return head
其他解法
兩次遍歷法:第一次遍歷求串列長度 n,計算從尾數第 k 個即從頭數第 n-k+1 個,第二次遍歷找到兩個目標節點。時間 O(n),空間 O(1),邏輯更直觀但需要兩次遍歷。
儲存所有節點:將所有節點存入陣列,直接以索引存取兩個目標節點並交換值。時間 O(n),空間 O(n),簡單但空間效率差。
延伸思考
- 如果題目要求實際交換節點(而非只交換值),解法需要如何修改?需要幾個額外指標?
- 此題與「找鏈結串列倒數第 k 個節點」的技巧相同,能否推廣到同時找多個不同位置的節點?
- 如果 k 可能超過串列長度(即非法輸入),如何在程式碼中加入邊界保護?