wonder/leetcode-go

Fork 0

Files

T

wonder dd46cffab1 vault backup: 2026-05-16 18:12:04

2026-05-16 18:12:04 +08:00

13 KiB

Raw Permalink Blame History

tags, create time

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`	把整段接回主链	如果没有这一步，交换后的段落就从主链上脱落了

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]）：

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) — 只用了有限个指针变量。

方法二：递归法

递归的思路更抽象但极其简洁：假设后半段已经处理好，我只管搞定第一对，然后把剩下的链接上去。

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→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`

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 个一组翻转、奇偶重排等。模式为：

检查是否还有足够节点继续分组

用局部变量拿到每组的头和尾

组内反转/调整

组的头部接到递归结果

返回新的头部

[!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 环境内置如下结构体定义：

type ListNode struct {
    Val  int
    Next *ListNode
}

不需要手动定义，直接在解题中使用即可。

[!info] 📊 两种方法对比

维度	迭代法 ⭐	递归法
时间复杂度	O(n)	O(n)
空间复杂度	O(1)	O(n)（递归栈）
代码行数	循环体约 7 行	核心逻辑约 6 行
直观程度	高（一步步模拟交换过程）	中等（需理解假设正确性）
面试推荐	⭐⭐⭐ 首选	⭐⭐ 可作为进阶展示
适用场景	通用，无栈溢出风险	适合教学和理解分组思想

[!success] ✅ 相关题目串联

这题是后续更多分组类链表操作的基础模板：

25-K 个一组翻转链表 — K 个一组的泛化版本

奇偶链表 — 按奇偶位置分组

同一思想的变体还出现在数组的两两配对问题中

代码

迭代法（虚拟头节点）⭐

/**
 * 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 // 绕过虚拟头节点，返回真正的头节点
}

递归法

/**
 * 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 个节点」这道同级别的题目，"两两交换"的核心难度在于多指针同时操作的顺序控制——任何一个赋值的先后颠倒都可能导致断链或死循环。掌握这个四步重组模板后，面对任何涉及局部结构调整的链表问题都会更加从容。建议先用纸笔画出指针变化图，再动手编码。

13 KiB Raw Permalink Blame History Unescape Escape