两两交换链表中的节点
Swap Nodes in Pairs
把链表中相邻的两个节点两两交换，不能只交换值；落单节点保持原位。
在力扣中练习题目描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
解题思路
哨兵 + 三根指针 · 迭代
每组只改三条 next，改完把 prev 移到组尾
相邻交换不是把值对调，而是真的改指针。每一组涉及三个节点：前驱 prev、组内第一个 first、第二个 second。
修改顺序很关键：先让 first->next 越过 second，保住后面的链；再让 second->next 指回 first；最后让 prev->next 接上新的组头 second。
first(node-0).next 越过 second，改指 node-2。
dummy 哨兵让第一组也有“前驱”，不需要单独处理头节点。每轮结束后 prev 移到本组原来的 first，它现在是下一组的前驱。
自拟主例有 5 个节点，两对交换后还剩最后一个；循环条件要求 prev->next 和 prev->next->next 都存在，落单节点因此不会被误动。
second(node-3).next 指回 first，组内顺序反转。
每个节点只被访问一次，额外空间 O(1)。
易错点
- 先改 second->next：first 原来的 next 丢失，后面整段链断掉。
- 忘记把 prev 移到 first：下一轮还在旧位置，会重复交换同一组。
- 循环只检查 prev->next：只剩一个节点时访问 second->next 会空指针。
- 直接交换 val：题目要求交换节点，值相同或节点带额外字段时会出错。
递归 · 交换后接剩余
交换前两个，剩下的交给递归
代码最短，但递归深度约 n/2，链表很长时需要 O(n) 调用栈；仅作对照。
递归只关注当前两个节点：若不足两个直接返回。否则记下 second，让 head->next 指向“后面部分交换后的结果”，再让 second->next = head，返回 second。
它和迭代版做的是同一件事，只是把“继续下一组”交给调用栈。代码短、可读性好，但递归深度随链表长度增长。
如果面试官追问空间复杂度，要明确说明递归栈也是 O(n)，不能声称 O(1)。
- 1不足两个节点，直接返回 head。
- 2记下第二个节点 second。
- 3递归交换 second 之后的部分，接到 head 后面。
- 4second 指向 head，返回 second。
易错点
- 递归前没有保存 second：交换后找不到新的组头。
- 把 head->next 直接设为 second->next：后面的节点没有继续交换。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
head = [7,2,9,4,5]dummy 指向原头，prev 先停在 dummy；每次处理 prev 后面的两个节点。
查看 C++ 代码
延伸阅读
- 链表改边的题目，先画出“改之前”和“改之后”的局部图，再决定三条边的修改顺序。
- 哨兵节点 + 局部三指针，是 k 个一组反转（25 题）的基础版本。