24. 两两交换链表中的节点 (Medium)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/swap-nodes-in-pairs/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部值的情况下完成本题（即只能进行节点交换）。
示例：
- 输入：head = [1,2,3,4]
- 输出：[2,1,4,3]
题目详细分析
- 数据范围： 链表中节点数在 [0, 100] 范围内，节点值在 [0, 100] 范围内
- 输入特征： 单链表，需要成对交换，不修改节点值
- 核心约束： 必须实际交换节点（修改 next 指针），不能只交换节点值
- 隐藏条件： 如果节点数是奇数，最后一个节点保持不变。每对交换涉及三个连接的修改
- 边界条件： 空链表、只有一个节点、奇数个节点（最后一个不需要交换）
小白版直白理解
就像把一排人两两分组，每一组的两个人交换位置。第一个人站到第二个人的位置，第二个人站到第一个人的位置。
因为链表只有单向的「指向」关系，不能直接把两个人互换那么粗暴。我们需要小心地重新系好每一根绳子。为了不搞乱，最好在纸上画图，标清楚每一步指针应该怎么重新指向。
解题思路
思路一：迭代法 + 虚拟头节点（推荐）
为什么这样想： 每次交换两个节点，需要知道这两个节点的前驱。第一对没有前驱，所以用虚拟头节点作为统一前驱。画图理解指针重指向是关键。
关键洞察： 交换一对节点 (p1, p2) 涉及 3 条指针的修改：
- pre.next 指向 p2（p2 成为第一个）
- p1.next 指向 p2.next（p1 与后续连接）
- p2.next 指向 p1（p2 指向 p1）
def swapPairs(head):
"""迭代法：虚拟头节点 + 三步交换"""
dummy = ListNode(0, head)
pre = dummy
# 每次检查是否有两个节点可以交换
while pre.next and pre.next.next:
p1 = pre.next # 第一个节点
p2 = p1.next # 第二个节点
# 三步交换
pre.next = p2 # ① 前驱指向 p2
p1.next = p2.next # ② p1 指向 p2 的后继
p2.next = p1 # ③ p2 指向 p1（完成交换）
pre = p1 # pre 移到下一对的前驱（即 p1）
return dummy.next思路二：递归法
思路讲解： 将问题分解为：交换前两个节点，然后递归处理剩下的链表。递归返回的是「已处理完的链表头」，将其接到第一个节点（交换后变成了第二个节点）的后面。
关键洞察： 递归法的终止条件是空或只有一个节点。每次递归需要返回新的一对的「头节点」（即原来的第二个节点）。
def swapPairs(head):
"""递归法"""
# 终止条件：空或只有一个节点
if not head or not head.next:
return head
# 保存要交换的两个节点
first = head
second = head.next
# 交换：first 指向递归返回的结果
first.next = swapPairs(second.next)
second.next = first
# 返回新的头节点（原第二个节点）
return second易错点
- 三步交换的顺序： 必须按照 pre→p2 → p1→next → p2→p1 的顺序，不能乱。修改 pre.next 之前必须保证 p1、p2 已正确赋值
- pre 的移动： 交换后 pre 移到 p1（原第一个节点，现在是第二对的前驱），而不是移到 p2
- 循环条件：
while pre.next and pre.next.next检查是否有两个可交换的节点 - 奇数个节点： 最后一个节点不参与交换，自然保留在末尾
- 图解辅助： 强烈建议画图理解指针变化，链表指针操作光靠脑子想很容易出错
框架提炼
相邻交换三步模板： 适用于需要成对交换链表节点的场景。
# 在 pre 后交换 p1 和 p2 两个节点
p1 = pre.next
p2 = p1.next
pre.next = p2 # 前驱指向 p2
p1.next = p2.next # p1 指向后续
p2.next = p1 # p2 指向 p1
pre = p1 # 前进到下一对这个模板可以看作是 25 题「K 个一组翻转链表」在 K=2 时的特化实现。
关联题目
- 206-反转链表 — 链表翻转的基础操作
- 25-K个一组翻转链表 — 从两两扩展到 K 个一组，Hard 难度
- 92-反转链表II — 反转链表中的指定区间