1. 题目
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入： head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入： head = [] 输出：[]
示例 3：
输入： head = [1] 输出：[1]
2. 题解
2.1. 迭代
2.1.1. 核心思想
- 创建虚拟头结点 dummy，方便处理头节点交换
cur从 dummy 出发，每次交换后面两个节点- 设
cur -> node1 -> node2 -> next- node1.next = node2.next
- node2.next = node1
- cur.next = node2
- cur = node1 跳到下一组前
- 循环条件：
cur->next != nullptr && cur->next->next != nullptr
2.1.2. 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = dummy;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* node1 = cur->next;
ListNode* node2 = cur->next->next;
node1->next = node2->next;
node2->next = node1;
cur->next = node2;
cur = node1;
}
return dummy->next;
}
};2.1.3. 复杂度
时间复杂度： 空间复杂度：
2.2. 递归
2.2.1. 核心思想
- 递归函数返回交换完成后的子链表头
- base case：剩余 0 个或 1 个节点直接返回
- 交换当前两个节点，然后递归处理后面链表
2.2.2. 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr) {
return head;
}
ListNode* node2 = head->next;
head->next = swapPairs(node2->next);
node2->next = head;
return node2;
}
};2.2.3. 复杂度
时间复杂度： 空间复杂度：（递归栈）
2.3. 两种算法对比
| 对比项 | 迭代（虚拟头结点） | 递归 | ||
|---|---|---|---|---|
| 核心思路 | 用虚拟头，循环一对一对交换 | 把问题拆成：交换前 2 个，剩下递归处理 | ||
| 时间复杂度 | O(n) | O(n) | ||
| 空间复杂度 | O(1) 只几个指针，原地操作 | O(n) 递归调用栈开销 | ||
| 返回值 | 返回dummy->next | 返回交换后的新头node2 | ||
| 边界终止 | cur->next && cur->next->next | `head==nullptr | head->next==nullptr | |
| 优点 | 常数空间，无栈溢出风险，工程常用 | 代码短、逻辑简洁，写得快 | ||
| 缺点 | 指针步骤多，容易写错指针顺序 | 链表很长会栈溢出，不适合超长链表 | ||
| 适合场景 | 面试首选、生产代码 | 做题快速写，链表长度不大 |