--- tags: ["LeetCode", "链表", "迭代", "递归", "虚拟头节点", "中等"] create time: 2026-05-16 15:30 --- # 30-两两交换链表中的节点 ## 题面 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。**你必须在不修改节点内部的值的情况下完成本题**（即，只能进行节点交换）。 **示例 1：** ``` 输入：head = [1,2,3,4] 输出：[2,1,4,3] ``` **示例 2：** ``` 输入：head = [] 输出：[] ``` **示例 3：** ``` 输入：head = [1] 输出：[1] ``` **提示：** - 链表中节点的数目在范围 `[0, 100]` 内 - `0 <= Node.val <= 100` --- ## 思路 > [!question] 💡 核心洞察 > "两两交换"意味着我们要把 `A → B → C → D` 变成 `B → A → D → C`。每一次操作只涉及**两个一组**的节点对，组内互换、组间拼接。 ### 关键问题：三指针协作 > [!warning] ⚠️ 最大陷阱 > 交换两个相邻节点时，如果先改了其中一个的 `Next`，就会**丢失另一个节点的引用**。必须像处理断链风险一样，用额外变量保存需要保留的地址。 ### 一次交换的本质：四步重组 以交换节点 `A` 和 `B` 为例（`A` 在前，`B` 在后）： ``` 交换前：... → prev → A → B → next → ... ↑ ↑ ↑ prev A.Next=B B.Next=next ``` 要得到： ``` 交换后：... → prev → B → A → next → ... ``` | 步骤 | 动作 | 对应代码 | 为什么必须先做这步？ | |------|------|---------|------------------| | ① | **记录后继**：`tmp = B.Next` | 防止 B.Next 被覆盖后丢失后续链表 | 如果不保存，后面一步会把 B.Next 改掉，再也找不到 C 了 | | ② | **B 指向前驱**：`B.Next = A` | 建立 B→A 的反向连接 | 这是成对交换的核心——让后面的节点跑到前面去 | | ③ | **A 指向后继**：`A.Next = tmp` | 让 A 接到下一组的首节点 | A 原来是前面的节点，现在需要连到未处理的部分 | | ④ | **前驱接入 B**：`prev.Next = B` | 把整段接回主链 | 如果没有这一步，交换后的段落就从主链上脱落了 | ```mermaid flowchart LR subgraph Before["交换前"] P["prev"] --> A["A"] A --> B["B"] B --> N["next / C"] end subgraph Step1["① 记录后继: tmp = B.Next"] S1["tmp ← C"] end subgraph Step2["② B.next = A"] B2["B → A"] end subgraph Step3["③ A.next = tmp"] A2["A → C"] end subgraph Step4["④ prev.next = B"] P2["prev → B → A → C"] end Before --> S1 -.引导.-> Step2 -.引导.-> Step3 -.引导.-> Step4 style Before fill:#fff4e6,stroke:#f90 style Step4 fill:#d4edda,stroke:#28a ``` ### 方法一：迭代法 + 虚拟头节点 ⭐（最优） 用一个**虚拟头节点** `dummy` 简化边界处理（特别是第一个节点对的交换），然后用一个指针 `prev` 滑动推进。 **不变量：** 每一轮循环开始时，`prev.Next` 始终是一个待交换节点对的第一个节点。 **执行流程演示（`head = [1,2,3,4]`）：** ```mermaid flowchart TD Init["初始\ndummy→1→2→3→4\nprev=dummy"] --> Round1["第1轮: 交换 (1,2)\ndummy→2→1→3→4\nprev=1"] Round1 --> Check1{"prev.Next != nil &&\nprev.Next.Next != nil?"} Check1 -- 是 --> Round2["第2轮: 交换 (3,4)\ndummy→2→1→4→3\nprev=3"] Round2 --> Check2{"prev.Next != nil &&\nprev.Next.Next != nil?"} Check2 -- 否 --> Done["退出\nreturn dummy.Next ✅\n输出: [2,1,4,3]"] style Init fill:#bbf,stroke:#333 style Round1 fill:#f9d,stroke:#333 style Round2 fill:#f9d,stroke:#333 style Done fill:#d4edda,stroke:#28a ``` 逐步展开： | 轮次 | 链表状态 | prev | 说明 | |------|---------|------|------| | 初始 | `dummy→1→2→3→4` | dummy | prev 从虚拟头出发 | | 第 1 轮后 | `dummy→2→1→3→4` | 1 | 交换 (1,2)，prev 前进到 A(=1) | | 第 2 轮后 | `dummy→2→1→4→3` | 3 | 交换 (3,4)，prev 前进到 A(=3) | | 退出条件触发 | — | — | prev.Next == nil，退出循环 | > [!question] 💡 引导思考：为什么 prev 要前进到 A（被交换的后那个节点）而不是 B？ > 因为交换完成后，B 跑到了前面，A 到了后面。下一组节点紧跟在 A 之后（`A.Next` 就是下一组的开头）。所以 `prev = A` 恰好让它在下一轮可以正确访问 `prev.Next`（下一组的第一个节点）。 **时间复杂度：O(n)** — 每个节点被访问常数次。 **空间复杂度：O(1)** — 只用了有限个指针变量。 ### 方法二：递归法 递归的思路更抽象但极其简洁：**假设后半段已经处理好，我只管搞定第一对，然后把剩下的链接上去。** ```mermaid flowchart LR subgraph Recursion["整体递归框架"] R1["① newHead = head.Next\n(拿到第二节点)"] --> R2["② nextPair = newHead.Next\n(保存剩余部分起点)"] R2 --> R3["③ newHead.Next = head\n(第二节点指回第一节点)"] R3 --> R4["④ head.Next = swapPairs(nextPair)\n(第一节点接到递归结果)"] R4 --> R5["返回 newHead ✅"] end style R1 fill:#bbf,stroke:#333 style R5 fill:#d4edda,stroke:#28a ``` **递的过程：** 一直深入到没有足够的节点继续配对时停止（`head == nil` 或 `head.Next == nil`），返回当前 head。 **归的过程：** 每层负责三件事： 1. 确定这一组的第二个节点为新的局部头 2. 把自己的两个节点交换好 3. 把第一对的尾部接到递归返回的结果上 以 `1→2→3→4` 为例的完整递归栈： | 阶段 | head / newHead | nextPair | 执行的操作 | 返回值 | |------|---------------|----------|-----------|--------| | 递 | `head=3→4` | nil | 4.Next = 3；3.Next = swapPairs(nil) = nil | `4→3` | | 基准 | `head=nil` | — | 直接返回 `nil` | `nil` | | 归 | `head=1→2` | 3 | 2.Next = 1；1.Next = swapPairs(3→4) = 4→3 | `2→1→4→3` | ```mermaid flowchart TD Base["基准: swapPairs(nil) → nil\n(不足一对，直接返回)"] --> L1["L1: head=3→4, newHead=4\n① 4.Next = 3\n② 3.Next = swapPairs(nil) = nil\n结果: 4→3→nil, 返回 4"] L1 --> L2["L2: head=1→2, newHead=2\n① 2.Next = 1\n② 1.Next = swapPairs(3→4) = 4→3\n结果: 2→1→4→3, 返回 2 ✅"] style Base fill:#eee,stroke:#999 style L1 fill:#bbf,stroke:#333 style L2 fill:#d4edda,stroke:#28a ``` > [!info] 🧠 递归的两个参数直觉 > - **函数签名**：`func swapPairs(head *ListNode) *ListNode` —— 传入一段链表，返回这段链表两两交换后的头 > - **假设成立**：调用 `swapPairs(rest)` 时，我们**假设它已经正确完成了任务**，只管拿到它的返回值来衔接 > - 这就是递归最强大的地方——不需要想全貌，每次只处理眼前的一对 **时间复杂度：O(n)** — 共 n/2 层递归，每层 O(1)。 **空间复杂度：O(n)** — 递归栈深度为 n/2。 --- ## 代码提示 ### 迭代法伪代码 ``` // 创建虚拟头节点 dummy = &ListNode{Next: head} prev = dummy // 只要还有至少两个节点可以交换，就继续 while prev.Next != nil and prev.Next.Next != nil { first = prev.Next // 待交换的第一个节点 (A) second = prev.Next.Next // 待交换的第二个节点 (B) third = second.Next // 第三组的起始节点 // 四步重组 second.Next = first // B → A first.Next = third // A → C prev.Next = second // prev → B → A → C // prev 前进到已交换的第一对中的第二个（即 A） prev = first } return dummy.Next ``` ### 递归法伪代码 ``` func swapPairs(head): // 基准情况：不足两个节点，直接返回 if head == nil or head.Next == nil: return head // newHead 是第二节点，它就是这一对交换后的新头 newHead = head.Next // 递归处理剩余部分 rest = swapPairs(newHead.Next) // ① 第一对的第二个节点指向第一个节点 newHead.Next = head // ② 第一个节点接到递归结果 head.Next = rest return newHead ``` --- ## 技巧 > [!tip] 🔑 "三步旋转"记忆法（迭代法核心） > 两两交换本质上是在固定位置做一个**环形旋转**：`prev → A → B → next`。只需记住三条边的新方向： > - `B.Next = A`（向后翻） > - `A.Next = next`（跨过去） > - `prev.Next = B`（接回来） > 想象成一个三角形转了一圈。 > [!tip] 🔑 递归模板："搞一对，接尾巴" > 适用于所有**分组处理**的链表问题：K 个一组翻转、奇偶重排等。模式为： > 1. 检查是否还有足够节点继续分组 > 2. 用局部变量拿到每组的头和尾 > 3. 组内反转/调整 > 4. 组的头部接到递归结果 > 5. 返回新的头部 > [!warning] ⚠️ 常见错误 1：先改 A.Next 再取 B.Next > 如果写成 `first.Next = second.Next` 再去取 `second.Next`，看起来没错。但如果不小心写成 `first.Next = nil` 或其他操作，后面再用 `second.Next` 就会出错。**建议：第一步总是先全部读取所需节点到局部变量中。** > [!warning] ⚠️ 常见错误 2：prev 走错位置 > 交换完成后 prev 必须走到 A（原第一个节点，现在在第二位），而不是走到 B。因为 A 的 Next 指向下一组的开头，这样才能在下一轮正确定位。 > [!note] 🐹 Go 中的链表定义 > LeetCode 的 Go 环境内置如下结构体定义： ```go type ListNode struct { Val int Next *ListNode } ``` 不需要手动定义，直接在解题中使用即可。 > [!info] 📊 两种方法对比 | 维度 | 迭代法 ⭐ | 递归法 | |------|---------|--------| | 时间复杂度 | O(n) | O(n) | | 空间复杂度 | O(1) | O(n)（递归栈） | | 代码行数 | 循环体约 7 行 | 核心逻辑约 6 行 | | 直观程度 | **高**（一步步模拟交换过程） | 中等（需理解假设正确性） | | 面试推荐 | ⭐⭐⭐ 首选 | ⭐⭐ 可作为进阶展示 | | 适用场景 | 通用，无栈溢出风险 | 适合教学和理解分组思想 | > [!success] ✅ 相关题目串联 > - 这题是后续更多**分组类链表操作**的基础模板： > - [25-K 个一组翻转链表](./) — K 个一组的泛化版本 > - [奇偶链表](https://leetcode.com/problems/odd-even-linked-list/) — 按奇偶位置分组 > - 同一思想的变体还出现在 [数组的两两配对问题](./) 中 --- ## 代码 ### 迭代法（虚拟头节点）⭐ ```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func swapPairs(head *ListNode) *ListNode { dummy := &ListNode{Next: head} // 虚拟头节点，统一第一个节点对的边界处理 prev := dummy // prev 指向每一组待交换节点的前驱 for prev.Next != nil && prev.Next.Next != nil { first := prev.Next // A：当前对的第一个节点 second := prev.Next.Next // B：当前对的第二个节点 third := second.Next // C：下一组的起始节点 // 四步重组：prev → B → A → C second.Next = first // ① B 指向前驱对中的 A first.Next = third // ② A 指向下一组的起始 C prev.Next = second // ③ prev 接入 B，完成拼接 // prev 前进到已处理的这对中的 A 位置 // （A 现在是这对的末尾，Next 正好指向下一组的开头） prev = first } return dummy.Next // 绕过虚拟头节点，返回真正的头节点 } ``` ### 递归法 ```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func swapPairs(head *ListNode) *ListNode { // 基准情况：空链表或只剩一个节点，无需交换 if head == nil || head.Next == nil { return head } // newHead 是当前对的第二个节点，交换后将成为这一段的头 newHead := head.Next // 保存剩余部分的起始点（即下一对的第一节点） nextPair := newHead.Next // ① 把第二节点接到第一节点前面 newHead.Next = head // ② 递归处理剩余部分，并链接到当前第一节点的后面 head.Next = swapPairs(nextPair) // newHead 成为整个链表的头 return newHead } ``` > [!success] ✅ 运行验证 > 这是 LeetCode 第 24 题，通过率约 60%+。相比「删除倒数第 N 个节点」这道同级别的题目，"两两交换"的核心难度在于**多指针同时操作的顺序控制**——任何一个赋值的先后颠倒都可能导致断链或死循环。掌握这个四步重组模板后，面对任何涉及局部结构调整的链表问题都会更加从容。建议先用纸笔画出指针变化图，再动手编码。