題目連結(https://leetcode.com/problems/swap-nodes-in-pairs/description/)

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

第 24 天挑第 24 題，正好再熟悉一下 Linked list

1. Repeat（題目重複確認）

• 輸入：一個 Linked list
• 輸出：同一個 Linked list，但修改成已經交換過鄰近節點的型態
• 前提：有可能沒有節點存在
  • The number of nodes in the list is in the range [0, 100].
  • 0 <= Node.val <= 100 節點值可能為 0

2. Examples（舉例確認理解）

/**
**Input:** head = [1,2,3,4]
**Output:** [2,1,4,3]
**Input:** head = [1,2,3]
**Output:** [2,1,3]
**Input:** head = []
**Output:** []

3. Approach（解題思路）

方法 ：遞迴法

• 終止條件：如果頭或頭的下一個點空，就回傳頭（整個linked list)
  • 頭的下一個點空表示已經沒有可配對的節點，節點數為奇數
• 遞迴邏輯：
  • 設 node = head->next（第二個節點）
  • head->next = swapPairs(node->next) → 交換剩下的鏈表
  • node->next = head → 將第二個節點指向第一個節點
  • 返回 node 作為新的頭節點
• 時間複雜度：O(n), T(n)=T(n-2)+1 每次處理兩個節點
• 空間複雜度：O(n) 遞迴呼叫 swapPairs 函式，所以需要呼叫堆疊 (call stack) 來儲存每一次遞迴的函式，函式只會宣告固定的指標（最多 n/2 層）

4. Code（C++）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* node = head->next;
        head->next = swapPairs(node->next);
        node->next = head;
        return node;
    }
};

5. Test 範例

Input: head = [1,2,3,4]

第一次呼叫 swapPairs(head=1)

• head = 1, head->next = 2 → 不是 nullptr

• node = head->next = 2

• 執行：head->next = swapPairs(node->next) 即為swapPairs(head=3)

  → 進入下一層遞迴，node->next=head = 3

第二次呼叫 swapPairs(head=3)

• head = 3, head->next = 4 → 不是 nullptr

• node = head->next = 4

• 執行：head->next = swapPairs(node->next)

  → 進入下一層遞迴，head = nullptr（node->next = nullptr）

第三次呼叫 swapPairs(head=nullptr)

• head = nullptr → 達到終止條件
• 回傳 nullptr

回到第二層（head=3, node=4）

• head->next = swapPairs(node->next) → head->next = nullptr
• node->next = head → 4->next = 3
• 回傳 node → 回傳 4（作為新頭節點）
• 現在這層鏈表是 4 → 3 → nullptr

回到第一層（head=1, node=2）

• head->next = swapPairs(node->next) → head->next = 4

  現在 1->next = 4

• node->next = head → 2->next = 1

• 回傳 node → 回傳 2（作為新頭節點）

• 最終鏈表：2 → 1 → 4 → 3 → nullptr

指標關係示意

6. 相關題目與延伸概念

• **Reverse Nodes in k-Group Hard**
• **Swapping Nodes in a Linked List Medium**

7. 補充：語法＆注意事項

• 指針操作：

  • head->next = swapPairs(node->next);

    → 將第一個節點連接到後續交換後的鏈表

  • node->next = head;

    → 將第二個節點指向第一個節點

• 遞迴 vs 迭代：

  • 遞迴寫法更簡潔，但使用 O(n) 的堆疊空間
  • 迭代寫法空間優化到 O(1)，適合大鏈表

ps. 部分內容經 AI 協助整理