LeetCode【0024】两两交换链表中的节点

1 中文题目

给定一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例：

链表如上
输入：head = [1,2,3,4]
输出：[2,1,4,3]

输入：head = []
输出：[]

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 $[0,100]$ 内
• $0\le Node.val\le 100$

---

2 求解方法：迭代法

2.1 方法思路

方法核心

使用迭代方法，每次处理两个相邻节点。并通过虚拟头节点简化边界情况处理，使用临时变量保存需要交换的节点和下一对节点。

实现步骤

• 特殊情况处理：
  • 空链表直接返回null
  • 只有一个节点直接返回该节点
• 初始化：
  • 创建虚拟头节点dummy
  • 设置prev指向dummy
• 交换过程：
  • 保存当前要交换的两个节点first和second
  • 保存下一对要处理的节点next_pair
  • 执行节点交换的三个步骤
  • 更新指针位置

方法示例

输入：1->2->3->4
过程演示：1. 初始状态：
dummy->1->2->3->4
prev = dummy, head = 12. 第一次交换(1,2)：
a. first = 1, second = 2, next_pair = 3
b. 交换后：dummy->2->1->3->4
c. prev = 1, head = 33. 第二次交换(3,4)：
a. first = 3, second = 4, next_pair = null
b. 交换后：dummy->2->1->4->3->null
c. prev = 3, head = null4. 循环结束，返回dummy.next
最终结果：2->1->4->3

2.2 Python代码

class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:# 如果链表为空或只有一个节点，直接返回if not head or not head.next:return head# 创建虚拟头节点，简化边界情况处理dummy = ListNode(0)dummy.next = head# prev指向当前待交换节点对的前一个节点prev = dummy# 当还有节点对可以交换时继续循环while head and head.next:# 保存要交换的两个节点first = headsecond = head.next# 保存下一对要处理的节点next_pair = second.next# 交换节点对# 1. 将第二个节点指向第一个节点second.next = first# 2. 将前一个节点指向第二个节点（新的首节点）prev.next = second# 3. 将第一个节点指向下一对节点的开始first.next = next_pair# 更新指针，为处理下一对节点做准备prev = firsthead = next_pairreturn dummy.next

2.3 复杂度分析

• 时间复杂度：O(n)，n是链表节点数
  • 只需要遍历一次链表
  • 每个节点最多被访问一次
• 空间复杂度：O(1)
  • 只使用了常数个额外变量
  • 不需要额外的数据结构

---

3 题目总结

题目难度：中等
数据结构：链表
应用算法：迭代法