24. 两两交换链表中的节点
卡哥建议：用虚拟头结点，这样会方便很多。 本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。题目链接/文章讲解/视频讲解：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
做题思路：
链表有指针指向，更改节点的指向也就达到了交换节点的目的，假设有节点0（虚拟头节点)，节点1，节点2，节点3。让节点1和节点2进行交换，就是让节点0指向节点2，再让节点2指向节点1，再让节点1指向节点3。看视频就能知道卡哥的注意事项。
交换节点的函数代码：
1 bool swapPairs(LinkList &L){
2 LNode *dummyHead; // 设置一个虚拟头结点
3 dummyHead = L;// 将虚拟头结点指向链表，
4 LNode* cur = dummyHead; //
5 while(cur->next != NULL && cur->next->next != NULL)
6 {
7 LNode* tmp = cur->next; // 记录临时节点，比如，表示节点1
8 LNode* tmp1 = cur->next->next->next; // 记录临时节点，表示节点3
9
10 cur->next = cur->next->next; // 让节点0的下一个指向节点2，这个看的是指向
11 cur->next->next = tmp; // 让节点2的下一个指向temp，节点1，
12 cur->next->next->next = tmp1; // 让节点1的下一个指向节点3，现在顺序是：0，2，1，3
13
14 cur = cur->next->next; // cur移动两位，准备下一轮交换，刚开始是从节点1开始交换，之后从节点3开始交换
15 }
16 //dummyHead = dummyHead->next;//虚拟头节点不是真正的节点，它下一个才是，这里如果要看函数返回值是不是节点类型
17 return true;
18 }
这道题的完整代码
1 #include <stdio.h>
2 #include <malloc.h>
3 typedef struct LNode{ //定义单链表结点类型 //这种方式代码可读性更强
4 int data;//每个节点存放一个数据元素
5 struct LNode *next;//指针指向下一个节点
6 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体
7 bool InitList(LinkList &L) //初始化一个单链表（带头结点）
8 {
9 L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
10 if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点
11 return false;
12 L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点
13 return true;
14 }
15 bool swapPairs(LinkList &L){ //交换节点
16 LNode *dummyHead; // 设置一个虚拟头结点
17 dummyHead = L;// 将虚拟头结点指向链表，
18 LNode* cur = dummyHead; //
19 while(cur->next != NULL && cur->next->next != NULL)
20 {
21 LNode* tmp = cur->next; // 记录临时节点，比如，表示节点1
22 LNode* tmp1 = cur->next->next->next; // 记录临时节点，表示节点3
23
24 cur->next = cur->next->next; // 让节点0的下一个指向节点2，这个看的是指向
25 cur->next->next = tmp; // 让节点2的下一个指向temp，节点1，
26 cur->next->next->next = tmp1; // 让节点1的下一个指向节点3，现在顺序是：0，2，1，3
27
28 cur = cur->next->next; // cur移动两位，准备下一轮交换，刚开始是从节点1开始交换，之后从节点3开始交换
29 }
30 //dummyHead = dummyHead->next;//虚拟头节点不是真正的节点，它下一个才是，这里如果要看函数返回值是不是节点类型
31 return true;
32 }
33 bool InsertList(LinkList &L, int i, int e) //在第 i 个位置插入元素 e （带头结点）
34 {
35 if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个
36 return false;
37 LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点
38 p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点
39 int j = 0;//记录当前p指向的是第几个结点，从头结点0开始
40 while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环
41 {
42 p = p->next; //p指向下一个结点
43 j++;
44 }
45 if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置
46 return false;
47 LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e
48 s->data = e;
49 s->next = p->next; //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点
50 p->next = s; //将结点s连到p之后
51 return true; //插入成功
52 }
53 void ShowList(LinkList L) //显示
54 {
55 if(L->next == NULL)
56 printf("这是一个空表\n");
57 while(L != NULL)
58 {
59 L = L->next;
60 printf("%d ",L->data);
61 }
62
63 }
64 bool DeleteList(LinkList &L, int val)//删除表L中值为 val 的元素
65 {
66 LNode *p = L->next, *q = L, *s; //L是头节点，L->next是第一个有效节点
67
68 while(p != NULL) //从第一个有效节点开始循环找值为val的节点
69 {
70 if(p->data == val)
71 {//原本顺序 p,q,s
72 s = p; //找到要删除的节点的话，就先用节点s保存p ,
73 p = p->next;//更改p的指向，在删除思路里说过，现在顺序 s,q,p
74 q->next = p;//q的指向也要记得改
75 free(s); //释放原来p所在的节点，只不过现在变成了s
76 }
77 else
78 {
79 q = p;//没有找到的话，就依次遍历其他节点，有种交换的感觉
80 p = p->next;
81 }
82 }
83 return true;
84 }
85 int GetList(LinkList &L, int i)//按位查找，返回第 i 个元素（带头节点）
86 {
87 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
88 return 0;
89 LNode *p;
90 int j = 0;
91 p = L;
92 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
93 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
94 p = p->next;
95 j++;
96 }
97 return p->data;
98 } //平均时间复杂度为O(n)
99 int UpdateList(LinkList &L, int i, int num)
100 {
101 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
102 return 0;
103 LNode *p;
104 int j = 0;
105 p = L;
106 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
107 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
108 p = p->next;
109 j++;
110 }
111 p->data = num;
112 return p->data;
113 }
114 void Destroy(LinkList &L) //销毁单链表
115 {
116 LNode *p;
117 while(L != NULL)
118 {
119 p = L;
120 L = L->next;
121 free(p);
122 }
123 }
124 void ShowMenu()
125 {
126 printf("************************\n");
127 printf("***** 1,添加数据 *****\n");
128 printf("***** 2,删除数据 *****\n");
129 printf("***** 3,查找数据 *****\n");
130 printf("***** 4,修改数据 *****\n");
131 printf("***** 5,显示数据 *****\n");
132 printf("***** 6,交换节点 *****\n");
133 printf("***** 0,销毁并退出 ***\n");
134 }
135 int main()
136 {
137 LinkList L;//声明一个单链表
138 InitList(L);//初始化函数调用
139 int n = 0;
140 int num = 0;
141 int select = 0; //创建选择输入的变量
142 while (true)
143 {
144 //菜单调用
145 ShowMenu();
146 printf("请输入你的选择\n");
147 scanf("%d", &select);
148 switch (select)
149 {
150 case 1: //1,添加数据
151 printf("请输入元素个数：\n");
152 scanf("%d",&n);
153 printf("请添加元素：\n");
154 for(int i = 1; i <= n; i++)
155 {
156 scanf("%d",&num);
157 InsertList(L,i,num);
158 }
159 printf("数据添加成功！\n");
160 getchar();
161 break;
162 case 2: //2,删除数据
163 int val;
164 scanf("%d",&val);
165 DeleteList(L,val);
166 getchar();
167 break;
168 case 3: //3,查找数据
169 printf("查找的元素是：%d\n",GetList(L,1));
170 getchar();
171 break;
172 case 4: //4,修改数据
173 UpdateList(L,1,0);
174 printf("修改成功！\n");
175 getchar();
176 break;
177 case 5: //4,显示数据
178 printf("单链表的数据有：");
179 ShowList(L);
180 getchar();
181 break;
182 case 6:
183 swapPairs(L);
184 getchar();
185 break;
186 case 0: //0,退出
187 Destroy(L);
188 printf("单链表已销毁！");
189 printf("欢迎下次使用");
190 return 0;
191 break;
192
193 default:
194 break;
195 }
196 }
197 return 0;
198 }
运行结果：
19.删除链表的倒数第N个节点
卡哥建议：双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点，建议先看视频。
做题思路：
删除第几个节点会了，那删除倒数第几个节点，可以理解为，比如，有5个节点，1,2,3,4,5. 删除倒数第2个节点（4），那就是删除第 5-2+1个节点，即第4个节点（4）。
删除倒数第几个节点的代码：
1 bool DeleteList(LinkList &L,int n, int i)//删除表L中倒数第 i 个位置的元素
2 {
3 if(i < 1)
4 return false;
5 LNode *p;
6 p = L;
7 int j = 0;
8 while(p != NULL && j < n - i ) //循环找倒数第 i个节点。这里本来是 j<i-1,找第i-1个节点，代码做了改变
9 //比如，有5个节点，1,2,3,4,5. 删除倒数第2个节点（4），那就是删除第 5-2+1个节点，即第4个节点（4）。
10 {
11 p = p->next;
12 j++;
13 }
14 if(p == NULL) //i值不合法，导致第 n-i个节点根本在表中找不到
15 return false;
16 if(p->next == NULL) //第 n-i 个节点能找到，但是刚好第 n-i 个节点之后已无其他节点（第n-i-1结点和第n-i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
17 return false;
18 LNode *q = p->next; //p是第 n-i 个节点，p->next是之后的节点，也是第 n-i+1 个节点，令q指向被删除节点
19 p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 n-i+1个节点
20 free(q); //释放节s点的存储空间
21 return true;
22 }
为了便于利用链表总节点数n,所以我在主函数里的switch结构里的case1，把删除函数加进去了，完整的代码：
1 #include <stdio.h>
2 #include <malloc.h>
3 typedef struct LNode{ //定义单链表结点类型 //这种方式代码可读性更强
4 int data;//每个节点存放一个数据元素
5 struct LNode *next;//指针指向下一个节点
6 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体
7 bool InitList(LinkList &L) //初始化一个单链表（带头结点）
8 {
9 L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
10 if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点
11 return false;
12 L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点
13 return true;
14 }
15 bool InsertList(LinkList &L, int i, int e) //在第 i 个位置插入元素 e （带头结点）
16 {
17 if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个
18 return false;
19 LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点
20 p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点
21 int j = 0;//记录当前p指向的是第几个结点，从头结点0开始
22 while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环
23 {
24 p = p->next; //p指向下一个结点
25 j++;
26 }
27 if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置
28 return false;
29 LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e
30 s->data = e;
31 s->next = p->next; //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点
32 p->next = s; //将结点s连到p之后
33 return true; //插入成功
34 }
35 void ShowList(LinkList L) //显示
36 {
37 if(L->next == NULL)
38 printf("这是一个空表\n");
39 while(L != NULL)
40 {
41 L = L->next;
42 printf("%d ",L->data);
43 }
44
45 }
46 bool DeleteList(LinkList &L,int n, int i)//删除表L中倒数第 i 个位置的元素
47 {
48 if(i < 1)
49 return false;
50 LNode *p;
51 p = L;
52 int j = 0;
53 while(p != NULL && j < n - i ) //循环找倒数第 i个节点。这里本来是 j<i-1,找第i-1个节点，代码做了改变
54 //比如，有5个节点，1,2,3,4,5. 删除倒数第2个节点（4），那就是删除第 5-2+1个节点，即第4个节点（4）。
55 {
56 p = p->next;
57 j++;
58 }
59 if(p == NULL) //i值不合法，导致第 n-i个节点根本在表中找不到
60 return false;
61 if(p->next == NULL) //第 n-i 个节点能找到，但是刚好第 n-i 个节点之后已无其他节点（第n-i-1结点和第n-i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
62 return false;
63 LNode *q = p->next; //p是第 n-i 个节点，p->next是之后的节点，也是第 n-i+1 个节点，令q指向被删除节点
64 p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 n-i+1个节点
65 free(q); //释放节s点的存储空间
66 return true;
67 }
68 int GetList(LinkList &L, int i)//按位查找，返回第 i 个元素（带头节点）
69 {
70 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
71 return 0;
72 LNode *p;
73 int j = 0;
74 p = L;
75 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
76 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
77 p = p->next;
78 j++;
79 }
80 return p->data;
81 } //平均时间复杂度为O(n)
82 int UpdateList(LinkList &L, int i, int num)
83 {
84 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
85 return 0;
86 LNode *p;
87 int j = 0;
88 p = L;
89 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
90 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
91 p = p->next;
92 j++;
93 }
94 p->data = num;
95 return p->data;
96 }
97 void Destroy(LinkList &L) //销毁单链表
98 {
99 LNode *p;
100 while(L != NULL)
101 {
102 p = L;
103 L = L->next;
104 free(p);
105 }
106 }
107 void ShowMenu()
108 {
109 printf("************************\n");
110 printf("***** 1,添加并删除数据 *****\n");
111 printf("***** 3,查找数据 *****\n");
112 printf("***** 4,修改数据 *****\n");
113 printf("***** 5,显示数据 *****\n");
114 printf("***** 0,销毁并退出 ***\n");
115 }
116 int main()
117 {
118 LinkList L;//声明一个单链表
119 InitList(L);//初始化函数调用
120 int n = 0;
121 int num = 0;
122 int select = 0; //创建选择输入的变量
123 while (true)
124 {
125 //菜单调用
126 ShowMenu();
127 printf("请输入你的选择\n");
128 scanf("%d", &select);
129 switch (select)
130 {
131 case 1: //1,添加并删除数据
132 printf("请输入元素个数：\n");
133 scanf("%d",&n);
134 printf("请添加元素：\n");
135 for(int i = 1; i <= n; i++)
136 {
137 scanf("%d",&num);
138 InsertList(L,i,num);
139 }
140 printf("数据添加成功！\n");
141 printf("请输入要删除倒数第几个数：\n");
142 int i;
143 scanf("%d",&i);
144 DeleteList(L,n,i);
145 getchar();
146 //break;
147 //getchar();
148 break;
149 //case 2: //2,删除数据
150
151 case 2: //2,查找数据
152 printf("查找的元素是：%d\n",GetList(L,1));
153 getchar();
154 break;
155 case 3: //3,修改数据
156 UpdateList(L,1,0);
157 printf("修改成功！\n");
158 getchar();
159 break;
160 case 4: //4,显示数据
161 printf("单链表的数据有：");
162 ShowList(L);
163 getchar();
164 break;
165 case 0: //0,退出
166 Destroy(L);
167 printf("单链表已销毁！");
168 printf("欢迎下次使用");
169 return 0;
170 break;
171
172 default:
173 break;
174 }
175 }
176 return 0;
177 }
运行结果：
142.环形链表II
卡哥建议：算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
做题思路：主要考察两知识点：1，判断链表是否环； 2，如果有环，如何找到这个环的入口1，这个题先知道用快慢指针法做，如果把链表想象成一条直线，那快慢指针永远不会相遇，它们走过的路线合起来只能是直线；如果把链表想象成一条直线的末尾有个环，那快指针走得快，会先进入环里，等慢指针走到环入口，可能这时候快指针已经走了一会了也到环入口了，刚好和慢指针相遇，或者慢指针已经进入环了，快指针在环里也走得快，能追上慢指针，相遇。因为有环，所以相遇，因为相遇，所以有环。
2，这个看视频，会有一个公式，2(x+y) = xy + n(y+z)，假设快指针速度是慢指针的2倍，那时间相同的情况下，列比例式，路程比速度。关于公式 x = （n-1)(y+z)+ z，是指快指针在走了n-1圈后，x = z，从相遇点走z，和从起点0走x，从视频中的图里就能看到刚好在环入口处。这个相遇点是已经相遇的地方，x=z，只是推导出的，不是两个指针重新去走的。
这个题的代码只写函数的，先没写完整的代码。
1 ListNode *detectCycle(ListNode *head) {
2 ListNode* fast = head;
3 ListNode* slow = head;
4 while(fast != NULL && fast->next != NULL) {
5 slow = slow->next;
6 fast = fast->next->next; //快指针比慢指针快2
7 // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
8 if (slow == fast) {
9 ListNode* index1 = fast;
10 ListNode* index2 = head;
11 while (index1 != index2) {//不是相遇点
12 index1 = index1->next; //继续向后找
13 index2 = index2->next;
14 }
15 return index2; // 返回环的入口
16 }
17 }
18 return NULL;
标签：LNode,指向,int,随想录,next,链表,NULL,节点 From： https://www.cnblogs.com/romantichuaner/p/17591245.html