Q24 两两交换链表中的节点

作者收录于类别算法

2026-08-04 2026-08-04 约 2046 字预计阅读 5 分钟

题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。不能只改节点内部的值，必须实际交换节点。输入：1 → 2 → 3 → 4，输出：2 → 1 → 4 → 3。

1 我的想法

想写一个函数：接受一个起点，把后面的两个节点"翻转"一下。第一次草稿卡在：

while() 空条件、x 未定义，编译不过；
更关键的是：交换完一对之后，不知道这一对怎么接回前面的链、怎么连到下一对；
于是用 flag、heade 去补，越补越乱。

核心：两两交换 = 每次处理"一对"，但必须记住这一对的前一个节点 prev，否则交换完接不回去。用虚拟头 dummy 统一第一对。

2 简要回答

用虚拟头节点 dummy，维护指针 prev（当前这一对的前一个节点）。每一轮：

1
prev -> a -> b -> rest     交换成     prev -> b -> a -> rest

然后 prev 跳到 a（这一对的新尾巴），继续处理下一对。

时间复杂度 $O(n)$
空间复杂度 $O(1)$（迭代版；递归版为 $O(n)$ 栈空间）

3 为什么需要 prev

只交换 a、b 本身不难（a->next = b->next; b->next = a;），难的是把这一对接回前面的链。交换完成后，前面的链还指着原来的 a，必须把它的 next 改成 b——所以必须提前握着"这一对的前一个节点"。

这正好呼应"写一个函数接受起点"的想法：函数参数不应该是这一对的第一个节点，而应该是这一对的前一个节点。

4 虚拟头到底是不是"必须"的

不是必须的，它是把"头节点特判"变成"统一处理"的技巧。头节点特殊在：它没有前驱。凡是"通过前一个节点操作"的写法，头节点都没有前一个可用。

什么时候可以用 nullptr 当虚拟头，什么时候必须 new 一个真节点，看一件事——你要不要通过它修改 next：

场景	能不能用 nullptr	原因
反转链表：只读 pre（`cur->next = pre`）	可以	只是把 pre 的值赋给别人，pre 本身不参与修改
两两交换 / 删除节点：要写 prev->next（`prev->next = b`）	不行	`nullptr->next` 没法赋值，前一个节点必须真实存在

不引入 dummy 也能写 swapPairs，但第一对要单独特判：先手动交换 head 和 head->next，再进循环处理后面的对——多一段代码，多一个出错点。dummy 让第一对也走同一个 swapTwo，特殊 case 直接消失。

5 核心代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 交换 prev 后面的两个节点
// 调用前：prev -> a -> b -> rest
// 调用后：prev -> b -> a -> rest
void swapTwo(ListNode* prev) {
    ListNode* a = prev->next;
    ListNode* b = a->next;
    a->next = b->next;      // a 先接到 rest
    b->next = a;            // b 指回 a
    prev->next = b;         // 前面的链接上 b
}

ListNode* swapPairs(ListNode* head) {
    ListNode* dummy = new ListNode(0, head);  // 虚拟头，让第一对也有 prev
    ListNode* prev = dummy;
    while (prev->next != nullptr && prev->next->next != nullptr) {
        swapTwo(prev);
        prev = prev->next->next;   // 下一对的前一个节点 = a
    }
    return dummy->next;
}

用 1→2→3→4 走一遍：

1
2
3
dummy -> 1 -> 2 -> 3 -> 4
第 1 轮：dummy -> 2 -> 1 -> 3 -> 4，prev 跳到 1
第 2 轮：dummy -> 2 -> 1 -> 4 -> 3，prev 跳到 3

奇数个节点时，最后一对凑不齐（prev->next->next == nullptr），剩下的单个节点不动，天然正确。

6 递归版（呼应 Q206 的"信任"）

1
2
3
4
5
6
7
ListNode* swapPairs(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;  // 基例
    ListNode* second = head->next;
    head->next = swapPairs(second->next);   // 信任子问题：后面的已经交换好
    second->next = head;                    // 这一层只交换前两个
    return second;
}

基例 + “假设后面已交换好” + 只做一步——和反转链表的信任模型完全一样。

6.1 递归版逐层拆解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
swapPairs(1→2→3→4)
  ├─ head=1, second=2
  ├─ 先算 swapPairs(3→4)     ← 小问题 = 从第3个节点起的整段
  │    ├─ head=3, second=4
  │    ├─ swapPairs(nullptr)  ← 空链表 → 返回 nullptr（基例）
  │    ├─ 3->next = nullptr
  │    ├─ 4->next = 3
  │    └─ 返回 4             （3→4 已变 4→3）
  ├─ 回到第一层：1->next = 4   ← 4 接在 1 后面，链变成 1→4→3
  ├─ 2->next = 1              ← 最外层现在才交换 1 和 2
  └─ 返回 2                   （最终 2→1→4→3 ✓）

递归的箭头是从里往外接的：最深处的子调用先接好，再一层层回溯补上"前两个节点"的交换。每一层只保证前两个节点的顺序对，后面整段全部丢给子调用、信任它已排好——和反转链表、fib 是同一个归纳模型。不需要 dummy。

迭代 vs 递归的建链方向：
迭代版：从前往后建链，处理完一对推进 prev，需要 dummy 兜第一对。
递归版：从后往前组装，最深处先接好再回溯补前面的，不需要 dummy。

7 我的草稿为什么乱

1
2
while(){ ... }                    // 空条件，编译不过
new_cur->next = x;                // x 没定义

更本质的问题：交换完一对后，这一对的新尾巴（原第一个节点）必须接到下一对的头；草稿里没有 prev 这个概念，只能用 flag、heade 硬补，越补越乱。加了 prev + dummy 之后，flag 和 heade 都不需要了。

8 易错点

循环条件必须是 prev->next != nullptr && prev->next->next != nullptr：保证这一对真的有两个节点。
交换后 prev = prev->next->next，即这一对的新尾巴 a；写错位置会漏节点或死循环。
不要只交换 val：题目明确要求实际交换节点。
返回 dummy->next，不是 head（head 可能已经被换到第二位了）。

目录

Q24 两两交换链表中的节点

1 我的想法

2 简要回答

3 为什么需要 prev

4 虚拟头到底是不是"必须"的

5 核心代码

6 递归版（呼应 Q206 的"信任"）

6.1 递归版逐层拆解

7 我的草稿为什么乱

8 易错点

相关内容

目录

Q24 两两交换链表中的节点

1 我的想法

2 简要回答

3 为什么需要 prev

4 虚拟头到底是不是"必须"的

5 核心代码

6 递归版（呼应 Q206 的"信任"）

6.1 递归版逐层拆解

7 我的草稿为什么乱

8 易错点

相关内容

Q1314 矩阵区域和

Q142 环形链表II

Q160 链表相交

Q19 删除链表的倒数第N个节点

Q206 反转链表