两两交换链表中的节点
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1
示例 2
示例 3
示例 4
模拟答题者思考
1. 我先想暴力：把节点值复制到数组，两两交换数组元素再重建链表——能过，但题目要求「只能进行节点交换」，且多用了 O(n) 额外空间。
2. 重复在哪里？每次操作都是「把相邻两个节点的指针关系翻转」；下一对的前驱，恰好是「上一对交换后的尾节点」。
3. 设前驱 prev、待换对 first、second：三步翻转——prev.next = second，first.next = second.next，second.next = first；然后 prev = first 处理下一对。
4. 边界：链表为空或只有一个节点时无需交换；奇数个节点时最后一对只有 first，当 first.next 为空应直接退出。
5. 第一对交换会改变头节点——加 dummy 哨兵后，prev 从 dummy 出发，与删头节点、合并链表等题同一套路。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dummy | ListNode* | 定义：哨兵头节点，dummy.next = head维护：始终位于真实头节点之前，统一处理「第一对交换后新头节点」的边界 更新：创建后不再移动，最终返回 dummy.next |
prev | ListNode* | 定义：待交换相邻两节点的前驱指针 维护：每轮交换完成后， prev 应停在「刚交换完的那一对」的第二个节点（即原 first）更新：交换一对后 prev = first，下一轮从 prev.next 继续 |
first | ListNode* | 定义：当前待交换对中的第一个节点（prev.next）维护：与 second 构成相邻一对；交换后 first 成为该对的尾节点更新：每轮从 prev.next 读取；交换后通过 prev = first 进入下一对 |
second | ListNode* | 定义：当前待交换对中的第二个节点（first.next）维护：交换后 second 成为该对的新头，并接到 prev.next更新：每轮从 first.next 读取；若不存在则不足一对，循环结束 |
落码步骤
1. 创建哨兵 dummy = ListNode(0, head)，prev = dummy
2. 当 prev.next 与 prev.next.next 均非空时进入循环（保证有一对可换）
3. 令 first = prev.next，second = first.next
4. 翻转这一对：prev.next = second；first.next = second.next；second.next = first
5. 更新 prev = first，继续下一对；返回 dummy.next
代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head) # 哨兵，统一处理头节点交换
prev = dummy
while prev.next and prev.next.next:
first = prev.next
second = first.next
prev.next = second # 前驱接到新头 second
first.next = second.next # first 接到后续链表
second.next = first # second 指向 first，完成翻转
prev = first # prev 移到本对尾节点，准备下一对
return dummy.nextclass Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0, head); // 哨兵，统一处理头节点交换
ListNode* prev = &dummy;
while (prev->next && prev->next->next) {
ListNode* first = prev->next;
ListNode* second = first->next;
prev->next = second; // 前驱接到新头 second
first->next = second->next; // first 接到后续链表
second->next = first; // second 指向 first，完成翻转
prev = first; // prev 移到本对尾节点，准备下一对
}
return dummy.next;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
忘记 dummy 哨兵：第一对 1↔2 交换后新头是 2，没有哨兵时很难统一修改「头指针的前驱」。
翻转顺序写错：必须先让 prev.next = second，再改 first.next，最后 second.next = first；若先改 first.next 可能丢失 second 的引用。
循环后忘记 prev = first：否则 prev 仍指向已处理节点，会反复交换同一对或成环。
必测边界 Case
head = [] → []
head = [1] → [1]（不足一对，原样返回）
head = [1,2,3] → [2,1,3]（最后一对只有 3，不参与交换）