🔀 24.两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例
示例 1：
1
2
| 输入：head = [1,2,3,4]
输出：[2,1,4,3]
|
示例 2：
示例 3：
思路
基本思想
相当于两两交换节点，两个为一组，进行交换，所以可以申请一个虚拟头结点指向给定的链表
申请虚拟头结点的目的是为了解决第一个节点的逆置问题，这样可以让首元结点与后面的节点处理方式一样，申请虚拟头结点的方式为：
1
| ListNode *node=new ListNode(0);
|
这样才能申请一个正常的节点，之后就是两两逆置的思路，需要使用两个指针，完成逆置
逆置的代码为：
1
2
3
4
5
6
7
8
9
10
11
12
| p=node;
q=node->next;
while(p->next!=nullptr&&q->next!=nullptr){
//节点的两两逆转
p->next=q->next;
q->next=q->next->next;
p->next->next=q;
//节点的向后移动
p=q;
q=q->next;
}
|
必须加上p->next!=nullptr，否则会报错，举例为[1,2,3,4]，因为交换两次之后，p指向4，q指向nullptr，nullptr无法访问next，就会出现空指针异常，所以两个判断条件都需要同时满足
执行流程
- 初始化指针，分别为虚拟头结点以及两个辅助节点
- 执行逆置操作
- 返回虚拟头结点的下一个节点为最终的结果
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==nullptr)
return head;
ListNode *node=new ListNode(0);
node->next=head;
ListNode *p=nullptr;
ListNode *q=nullptr;
p=node;
q=node->next;
while(p->next!=nullptr&&q->next!=nullptr){
//节点的两两逆转
p->next=q->next;
q->next=q->next->next;
p->next->next=q;
//节点的向后移动
p=q;
q=q->next;
}
return node->next;
}
};
|
如果上述代码无法理解，可以尝试将p看成slow指针，q看成fast指针：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
//两个指针一前一后移动，从而使得节点可以两两交换
ListNode* swapPairs(ListNode* head) {
//链表中没有节点或者只有一个节点时不需要交换
if(head==nullptr||head->next==nullptr)
return head;
//到这里至少两个节点
ListNode* dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode* fast=dummyHead->next;
ListNode* slow=dummyHead;
while(fast!=nullptr&&fast->next!=nullptr){
//两个节点交换
slow->next=fast->next;
fast->next=fast->next->next;
slow->next->next=fast;
//移动指针，保持slow始终在待交换节点的前一个位置
slow=fast;
fast=fast->next;
}
return dummyHead->next;
}
};
|
需要一直保持slow指针在待交换的两个节点的前一个节点
总结
主要有两个需要注意的地方：
- 申请一个虚拟头结点用来让首元结点与其他节点的操作逻辑一样
- 弄清楚逆置的逻辑，while的循环条件缺一不可
