LeetCode 24. 两两交换链表中的节点
题目描述
题意分析
从链表头部开始，把节点按相邻的两个分组，每组内部交换位置，组与组的前后顺序保持不变。必须改变节点之间的连接，不能只交换节点值；返回交换后的头节点。
空链表和单节点链表不变。如果节点总数为奇数，最后落单的节点也保持原位。至少有两个节点时，原来的第二个节点会成为新头，因此原
head未必还是返回起点。
解法：哨兵节点迭代交换相邻节点
核心思路
[!blue]
每轮只重连一对相邻节点，但需要把交换后的组头接回前面。第一组没有真实前驱，可以先放置一个哨兵
dummy指向原头节点，令第一组和后续组都按“前驱接组头”的方式处理。
pre始终指向已经处理部分的尾节点，first = pre.next、second = first.next是下一组。原来的局部连接是pre → first → second → 后续链表，目标连接是pre → second → first → 后续链表。只需改动三条next，节点值和后续未处理部分都不变。先执行
first.next = second.next，让交换后要成为组尾的first接住后续链表；接着执行second.next = first，反转本组顺序；最后执行pre.next = second，把本组的新头接回已处理部分。这个顺序保证在覆盖second.next之前，后续链表已经有连接保留下来。交换后，原来的
first成为这一组的尾节点，也是下一组的前驱，因此令pre = first。这样每轮只处理尚未交换的节点，已完成的部分不会再被改动。当pre后不足两个节点时结束，落单节点已经连接在尾部，无需额外处理。
解题步骤
- 创建
dummy并令它指向head，把pre初始化为dummy。- 同时确认
pre.next和pre.next.next非空，保证本轮存在完整的一对节点。- 保存本组的
first、second，依次重连first.next、second.next、pre.next。- 将
pre移到交换后的组尾first，继续处理后面的一组。- 循环结束后返回
dummy.next，它始终指向实际新头。
代码实现
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode first = pre.next;
ListNode second = first.next;
// 先接住下一组，再翻转本组的两条连接。
first.next = second.next;
second.next = first;
pre.next = second;
// 交换后的第一节点成为组尾，下一组从它之后开始。
pre = first;
}
return dummy.next;
}
}
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre := dummy
for pre.Next != nil && pre.Next.Next != nil {
first := pre.Next
second := first.Next
// 先接住下一组，再翻转本组的两条连接。
first.Next = second.Next
second.Next = first
pre.Next = second
// 交换后的第一节点成为组尾，下一组从它之后开始。
pre = first
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$，
n为节点数，每轮处理两个节点、修改常数条连接。- 空间复杂度：$O(1)$，只使用一个哨兵节点和固定数量的指针。
关键点总结
[!green]
- 哨兵为第一组提供前驱，统一头节点变化与普通位置的重连。
- 先保留后续链表连接，再反转本组，最后把新组头接回前驱。
pre表示已处理部分的尾部，交换后应移动到原first。- 不完整的一组保持原连接，不需要拆开再接回。
解法：递归交换后续链表
核心思路
[!blue]
把递归函数定义为“将传入链表两两交换，并返回交换后的新头”。如果当前链表不足两个节点，就不存在完整的一对，直接返回原头；这也会保留奇数长度链表末尾落单的节点。
有完整一对时，保存第二个节点
second = head.next。本组后面的部分仍然是同一个问题，所以先对second.next开始的后缀递归，得到后缀交换后的新头。原
head交换后将成为本组尾节点，因此让head.next接向递归返回的后缀新头；再令second.next = head完成本组交换，最后返回second作为本层的新头。只要后缀已经正确交换，这两条连接就能得到整个链表的正确结果；递归逐次减少两个节点，最终一定到达空链表或单节点的边界。
解题步骤
head为空或head.next为空时，直接返回head。- 保存本组第二个节点
second，对second.next后面的链表递归交换。- 将递归返回的新头赋给
head.next，把本组尾部接回处理好的后缀。- 令
second.next = head，返回本组新头second。
代码实现
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode second = head.next;
head.next = swapPairs(second.next);
second.next = head;
return second;
}
}
func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
second := head.Next
head.Next = swapPairs(second.Next)
second.Next = head
return second
}
复杂度分析
- 时间复杂度：$O(n)$，每层递归处理一对节点，重连操作为常数次。
- 空间复杂度：$O(n)$，每次递归跳过两个节点，调用栈深度仍与链表长度成正比。
关键点总结
[!green]
- 递归返回值是后缀交换后的新头，必须接回当前组的尾部。
- 先保存第二个节点，再处理后缀，避免改变连接后失去本组的新头。
- 迭代显式维护前驱，递归通过返回新头完成重连；递归会额外占用线性栈空间。
易错点总结
[!yellow]
- 只检查存在第一个节点，落单时继续访问第二个节点会触发空指针错误。
- 未保存后续链表就先改
second.next，会丢失原后继；再用它更新first.next还可能形成环。- 迭代交换后令
pre = second，会停在本组头部，下一轮重复处理已经交换过的节点。- 递归把剩余链表处理好后，没有用它的新头更新
head.next，会丢失后缀的正确连接。- 返回原
head，会漏掉交换后的新头；迭代返回dummy.next，递归返回本组原第二个节点。- 只交换节点的值，输出看似相同但没有满足实际交换节点的要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 25. K 个一组翻转链表 | 困难 | 本题相当于k=2的分组反转，原题需要先确认每组是否有足够节点。 |
| 92. 反转链表 II | 中等 | 同样保存前驱和后继后重连局部链段，原题只反转指定区间。 |