題目描述:給定一個鏈結串列,兩兩交換相鄰節點,並回傳交換後的串列。不能只修改節點的值,必須實際交換節點本身。
解題思路:使用虛擬頭節點(dummy node)簡化邊界處理。維護一個 prev 指標指向每對節點的前一個節點。對於每對節點 first 和 second,執行三步指標操作:prev->next = second、first->next = second->next、second->next = first。迭代版本比遞迴版本更節省堆疊空間,但遞迴版本程式碼更簡潔。關鍵是每次處理完一對後,將 prev 移動到 first(即交換後的第二個節點),再繼續處理下一對。
時間複雜度:O(n) — 每個節點恰好被處理一次。
空間複雜度:O(1) — 迭代版本僅使用常數個指標;若用遞迴版本則為 O(n) 堆疊空間。
1. Create dummy node pointing to head 2. Set prev = dummy 3. While prev.next and prev.next.next exist: a. first = prev.next b. second = prev.next.next c. prev.next = second d. first.next = second.next e. second.next = first f. prev = first (move to end of swapped pair) 4. Return dummy.next
遞迴解法:swapPairs(head) 先遞迴處理 head->next->next,再交換 head 與 head->next。程式碼極為簡潔,但需要 O(n) 堆疊空間。
僅交換值:直接交換每對節點的 val 欄位,程式碼最簡單,但題目明確禁止此做法。