前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

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

示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：
输入：head = []
输出：[]
示例 3：

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

提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

1. 交换链表(指针法)

思路

1. 定义链表结构的结构体struct。
2. 一个虚拟头节点。
3. 三个struct类型的指针，分别是cur，tmp，tmp1，cur作为指向节点，tmp和tmp1作为暂时指向节点，tmp是cur的下一个节点，tmp1是cur的下一个下一个下一个(3个next)节点。

2. 本题思路分析：

1. 创建虚拟头节点，这样对于所有的节点处理思路都一致了。
2. 让tmp指向cur的next,tmp1指向cur的next的next的next。
3. 让cur的next指针指向next的next节点。（如果之前不设置tmp指向cur的next，此时cur的next原本指向的节点就永远找不到）
4. 此时cur的next的next指向tmp,这样就完成了两个节点位置的交换。
5. 接下来就是让交换完毕的第二个节点指向下一个节点（这个下一个节点是之前tmp1指向的节点）。也就是向cur的next的next的next赋值为tmp1
6. 最后移动cur2次,让他到下一组两两交换的之前的一个节点上（上一组两两交换的第2个节点上）。

3. 算法实现

• 代码：

#include
#include
using namespace std;
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){}
};
ListNode* swapPairs(ListNode* head) {
	ListNode* dummy = new ListNode();
	ListNode* cur = dummy;
	dummy -> next = head;//易错点 虚拟头节点下一个是头结点  别忘了 
	while(cur -> next != nullptr && cur -> next -> next != nullptr){
		//辅助节点 
		ListNode* tmp = cur -> next;
		ListNode* tmp1 = cur -> next -> next -> next;
		//移动两个节点 
		cur -> next = cur -> next -> next;
		cur -> next -> next = tmp;
		cur -> next -> next -> next = tmp1;
		//移动cur 
		cur = cur -> next -> next;		
	}
	head = dummy -> next;
	delete dummy;
	return  head;
}
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
26
27
28
29

4. 算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

5. 算法坑点

1. 创建虚拟头节点dummy时，要记得赋值dummy->next指向原本的开始节点head。