前言知识点
链表的调试技巧
int main()
{
struct ListNode* n1=(struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2=(struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3=(struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4=(struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5=(struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
n1->next=n2;
n2->next=n3;
n3->next=n4;
n4->next=n5;
n5->next=NULL;
n1->val=1;
n2->val=2;
n3->val=3;
n4->val=2;
n5->val=1;
while(newhead!=NULL)
{
cout << newhead->val << "->" ;
newhead=newhead->next;
}
cout << "NULL" << endl;
return 0;
}手搓一个链表出来，方便观察我们的调试与结果
一、移除链表元素（俩个方法）
1.1题目链接
203. 移除链表元素 - 力扣（LeetCode）
1.2题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点。
1.3解题思路
思路1
遍历链表，比对每一个节点的数据与val是否相等，如果相等，就free掉该节点。
时间复杂度：O(N) ；空间复杂度：O(1)
易错点（1.如果head->val就是val，那么head得更新 2.小心free的时候找不到next）
1、当链表的头结点的数据等于val时，我们free掉该节点后需要挪动head指针，让其指向新的头结点；
2、我们在遍历链表的时候需要记录前一个节点的地址，因为当我们free掉当前节点之后，我们要让前一个节点的next；链接到当前节点的下一个节点；
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* cur =head;
struct ListNode* prev=NULL;//不用担心prev的节点更新问题
while(cur)
{
if(cur->val==val)
{
if(cur==head)//头就得动手术，更新头节点
{
head=cur->next;
free(cur);
cur=head;
}
else
{
prev->next=cur->next;//意志遗传 prev越过6指向3
free(cur);
cur=prev->next;//cur到了3这个位置，还是比prev快一步
}
}
else
{
prev=cur;//保证当没有节点删除的时候，起码prev在cur上
cur=cur->next;//先把prev带到这里，然后自己又偷偷走一步，保证相对位置
}
}
return head;
}
思路2
遍历链表，将不等于val的节点尾插到一个新的链表，将等于val的节点free掉。
时间复杂度：O(N) 空间复杂度：O(1)
难就难在我想不到用尾插，而是一位的改变指针指向，这令我非常晕乎乎
易错点
1、由于我们是把原链表中的节点尾插到新链表中去，所以我们插入元素的时候需要判断链表是否为空，如果为空，我们需要改变新链表的头结点；（这样的尾插并不方便）
2、当然，我们也可以把我们的新链表设计为带哨兵位的，这样我们直接进行尾插就行，但是要注意我们返回的应该是guard->next，因为哨兵位头结点不用于存储数据，同时在return之前记得把哨兵位头结点释放掉；
但要小心： newhead->next不要随便给别人赋值，这是一个随机值！！！（等到下面的反转链表就可以看到异常了）
3、由于原链表中最后一个节点的数据可能等于val，所以我们需要将新链表中尾结点的next置为NULL，防止通过它来访问已经被释放掉的节点。（这样的藕断丝连是会出问题的）
从代码逻辑中看出：最后一个是6的时候，cur=cur->next，也即是说把6直接给忽略掉了，并没有有效的删除，但是5->next还是指着6节点位置
struct ListNode* removeElements(struct ListNode* head, int val) {
if(head==NULL)
{
return NULL;
}
struct ListNode* cur =head;
struct ListNode* prev=NULL;//不用担心prev的节点更新问题
//因为要尾插，不想用tail了，定义一个Guard
struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail=newhead;
while(cur)
{
if(cur->val!=val)
{
tail->next=cur;//更新尾节点链接
//newhead->next=cur; 头节点别动！！！因为这个题不像反转链表，反转链表的newhead往前更新，因为箭头的指向在改变，所以头的改变到时候到了末尾正好是正确的
tail=cur;//更新尾节点位置
cur=cur->next;
}
else
{
cur=cur->next;
// struct ListNode* next = cur->next;
// free(cur);
// cur = next;
//杭哥这样删除是为了防止内存泄漏，但我直接往下一步走了
}
}
tail->next=NULL;//这句是一个大bug
head=newhead->next;
free(newhead);
return head;
}
（我这里cur节点偷了点懒，没有真正的free节点，这样会造成内存泄漏，虽然AC了，但是会有大问题，所以还是得多加小心！）
二、反转链表（俩个方法）
2.1题目链接
206. 反转链表 - 力扣（LeetCode）
2.2题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
2.3思路分析
思路1（利用迭代的思路）
指针的定义刚开始就是很有讲究的：
所以我们将n3定义在循环中，这也是我们常用的套路
n2负责改变指针指向，n3负责前进并且记录位置防止丢失，n1是用来告知n2指向哪里
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* n1=NULL;
struct ListNode* n2=head;
while(n2)
{
struct ListNode* n3=n2->next;
n2->next=n1;
n1=n2;
n2=n3;
}
return n1;
}思路2
将原链表中的节点头插到新链表中，然后返回新链表的头。（因为一直头插就可以改变链表顺序）
时间复杂度：O(N) 空间复杂度：O(1)
但是头插也有易错点：
1.记得更新头
2.记得定义一个next，要不然cur回不到原来的位置
3.还要小心空指针解引用的问题
//法二：取出链表的每一个节点头插
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
三、 链表的中间节点（如果只让遍历一次，怎么办？）
3.1题目链接
876. 链表的中间结点 - 力扣（LeetCode）
3.2题目描述
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。时间复杂度：O(N) 空间复杂度：O(1)
3.3思路分析
思路1
遍历两遍数组，第一遍求出链表长度，第二步找出链表的中间节点并返回。
代码实现
//法一：遍历两次链表，第一次找出链表有几个节点，第二次返回链表的中间节点
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* cur = head;
int count = 0;
while(cur)
{
count++;
cur = cur->next;
}
cur = head;
count /= 2;
while(count--)
{
cur = cur->next;
}
return cur;
}
思路2
由于这道题用第一种方法实现十分简单，所以在面试中面试官会加一个限制条件：要求只能遍历一遍链表；这时候就只能用快慢指针来解题了；
快慢指针：定义两个指针 – fast slow，慢指针一次走一步，快指针一次走两步；当链表长度为奇数，fast->next == NULL时，slow 为中间节点；当链表长度为偶数，fast == NULL 时，slow 为中间节点。时间复杂度：O(N) 空间复杂度：O(1)
快慢指针对于寻找节点是一把好手，我们一定要合理运用这种思维逻辑！
但是我们也还是得画出奇数偶数的情况
可以看出，对于奇数和偶数我们的fast指针一个在末尾，一个在NULL，所以只要我们while(fast && fast->next==NULL) 这样控制一下就可以兼容俩种情况啦~ 一定要多画图！！
易错点
我们在写while循环的条件时，必须写成 fast && fast->next，不能写成 fast->next && fast，因为当链表长度为偶数时，后面这种写法会发生空指针的解引用。
而且还有我们的while循环内部的逻辑是 && 我刚开始理解的是 || 但这样是不对的
//法二：使用快慢指针，slow一次走一步，fast一次走两步，只遍历一遍数组
//奇数个节点时，当fast->next == NULL时，slow刚好到达中间节点
//偶数个节点时，当fast == NULL时，slow刚好达到中间节点
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* fast, *slow;
slow = fast = head;
//注意：while条件中fast一定要写前面，不然偶数个时fast->next会造成空指针解引用
while(fast && fast->next) //节点是奇数还是偶数未知注意：
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
四、链表中倒数第K个节点
4.1题目链接
链表中倒数第k个结点LEETCODE
4.2题目描述
输入一个链表，输出该链表中倒数第k个结点。
4.3思路分析
看到求节点问题，脑子里立马想到快慢指针法
但很明显的是，对于链表而言，往回找是非常困难的，所以就让fast走的时候，让slow也走，保持二者的相对距离
int kthToLast(struct ListNode* head, int k){
struct ListNode* slow=head;
struct ListNode* fast=head;
if(head->next==NULL)
{
return head->val;
}
while(k--)
{
fast=fast->next;
}
while(fast)
{
slow=slow->next;
fast=fast->next;//这里会出现空指针的解引用！！！
}
return slow->val;
}这个题难就难在最后的特殊情况得特判一下，因为fast=fast->next，当只有一个节点的时候，会出现空指针的解引用
4.4心得
五、合并两个有序链表
5.1题目链接
21. 合并两个有序链表 - 力扣（LeetCode）
5.2题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
5.3思路分析
大思路：创建新节点，不断更新tail->next取最小值进行尾插，当没有的时候，tail->next的next可以直接将整个链表接手
在数组中有一个类似的题目：88. 合并两个有序数组 - 力扣（LeetCode）（顺序表博客有讲，用三个指针，从后往前比较）
时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、由于我们是把原链表中的节点尾插到新链表中去，所以我们插入元素的时候需要判断链表是否为空，如果为空，我们需要改变新链表的头结点；
2、当然，我们也可以把我们的新链表设计为带哨兵位头的，这样我们直接进行尾插就行，但是要注意我们返回的应该是guard->next，因为哨兵位头结点不用于存储数据，同时在return之前我们要记得把哨兵位头结点释放掉；
3、我以为尾插的时候加上guard头节点就不需要定义tail指针了，其实是我对结构的熟悉程度不够，我们的tail是必须得定义好的！！！！
4、插入的时候，我发现如果我把第一个链表的遍历拿下来赋值的话，它很容易就找不到下一个位置了，所以俩个while循环中都必须有next指针变量
等等等等
注意：循环体内的next指针可以不用定义！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//取小的尾插
struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* l1=list1,*l2=list2;
//guard->next=NULL;
struct ListNode* tail=guard;
while(l1 && l2)
{
if(l1->val <= l2->val)
{
struct ListNode* next=l1->next;//方便l1可以回去原来的链表继续遍历
tail->next=l1;//不断更新，只要最小的
tail=l1;//tail向前移动一下
l1=next;//l1继续回去遍历原先的链表
}
else
{
struct ListNode* next=l2->next;//方便l2可以回去原来的链表继续遍历
tail->next=l2;//不断更新，只要最小的
tail=l2;//tail向前移动一下
l2=next;//l2继续回去遍历原先的链表
}
}
if(l1==NULL)
{
tail->next=l2;
}
else
{
tail->next=l1;
}
//最后将guard释放，更规范
struct ListNode* head = guard->next;
free(guard);
guard = NULL;
return head;
}六、分割链表（特殊情况多）
6.1题目链接
86. 分隔链表 - 力扣（LeetCode）
6.2题目描述
分隔链表分为初阶版和进阶版，初阶版不要求我们保留每个分区中各节点的初始相对位置，而进阶版则要求要求我们保留每个分区中各节点的初始相对位置，这里我们讲解进阶版。
6.3思路分析
大思路是由于尾插不改变相对顺序，所以我们分别进行俩次尾插，再链接起来
eg：4 2 1 6 8 0 7这组数据，x==5 来进行分割
那么分割完毕后的样子是：4 2 1 0 6 8 7 我们画图进行演示
最后将这二者连接起来就大功告成
易错点
先说情况一和情况二：
感觉其实也大同小异，还是不往这方面想了，反正就是如果需要尾插，为了避免许多边界条件的处理，使链表的操作更加简洁和清晰，我们就创建头节点
通过下面的代码易错可以得知：如果不写头，还是很麻烦的，因为带头很容易控制随机值
情况四：
我们的lesstail已经指向了新节点，但是我们的2虽然乖乖的跟在了小节点元素队伍中去，但是我们的7节点与它仍有藕断丝连，所以我们必须断掉（但是合并俩个链表不一样，我们并不担心他们的藕断丝连，因为我们在while循环中一直更新tail的next指针节点）
这个易错点有点像移除链表元素的思路2时候那个一样，小伙伴们可以翻上去看看
代码易错点补充：
//LessGuard->next=NULL;
GreaterGuard->next = NULL;
//这俩个赋予空值看起来没有意义，但其实用处很大，因为我们下面有一个赋值操作
因为我们的节点是malloc出来的，也就说明里面都是随机值
LessTail->next=GreaterGuard->next;//将俩个链表连接起来如果都是比 x 小的元素，那么GreaterGuard内部 else 就无法进去 ，cur 就无法给其赋值，那么如果不初始化的话就是随机值，这会引发巨大的错误！！！
（=左值不初始化不会报错，但是右值没有初始化会报一个非常大的错误，直接无法通过）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode* LessGuard=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* GreaterGuard=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=head,*LessTail=LessGuard,*GreaterTail=GreaterGuard;
//LessGuard->next=NULL;
GreaterGuard->next = NULL;
//这俩个赋予空值看起来没有意义，但其实用处很大，因为我们下面有一个赋值操作
if(head==NULL)
{
return NULL;
}
if(head->next==NULL)
{
return head;
}
while(cur)
{
//struct ListNode* next=cur->next;
//因为我们这个题并没有修改cur的值，所以不需要next变量让我们回去
if(cur->val < x)
{
LessTail->next=cur;
LessTail = cur;
cur=cur->next;
}
else
{
GreaterTail->next=cur;
GreaterTail=cur;
cur=cur->next;
}
}
LessTail->next=GreaterGuard->next;//将俩个链表连接起来
GreaterTail->next=NULL;//避免藕断丝连
//释放哨兵位头结点
//head = LessGuard->next;
// free(GreaterGuard);
// free(LessGuard);
// GreaterGuard = NULL;
// LessGuard = NULL;
return LessGuard->next;
}
七、回文链表（不可以开辟新空间）
7.1题目链接
234. 回文链表 - 力扣（LeetCode）
7.2题目描述
给定一个链表的 头节点 head ，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
7.3思路分析
大思路：
1.找到链表的中间节点，将链表中间及以后的节点反转(中间节点用快慢，反转用头插或者用迭代n1，n2，n3)
2.然后用两个指针，一个指向链表开头，另一个指向反转部分的开头
3.cur指向原先的链表，遍历观察二者的val是否相等。
时间复杂度：O(N) 空间复杂度：O(1)
易错点：
我们反转的是中间及以后的节点，但是并未改变中间节点的前一个节点的next；也就是说，中间节点的前一个节点指向的是反转后的链表的最后一个节点；所以不管是链表长度是奇数还是偶数，我们都可以直接判断指针指向节点的val是否相等。
但是在写代码的时候，这个奇偶性还是很磨人的
但是很难受的是，直接写出数字并不可以很好的反映出链表内部的结构，以及那些元素连接在了一起，所以我们先来分析一下1 2 3 2 1反转之后的链表情况
这个时候再来分析cur和 rmid 的关系就很好理解了
很幸运的是，奇数这里有一个自己比较自己的一个效果（我刚开始没有分析出来head的链表元素为1 2 3 把我痛苦了好久）
奇数解决了，那么偶数就更简单啦！只需要一个一个往后走，一旦遇到不合适的咔嚓结束就好啦
最后放一个情况总结图：
希望看到这里大家可以明白我们的循环条件如何把控（快吐血的我...）
反正想要强调的就一件事：中间节点后面的链表反转完之后，我们的中间节点的前一个位置与原先后面的节点仍然有关系！
完整代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast && fast->next)
{
slow=slow->next;//slow走一步
fast=fast->next->next;//fast走俩步
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* n1=NULL;
struct ListNode* n2=head;
while(n2)
{
struct ListNode* n3=n2->next;
n2->next=n1;
//迭代
n1=n2;
n2=n3;
}
return n1;
}
bool isPalindrome(struct ListNode* head)
{
struct ListNode* rmid=(reverseList(middleNode(head)));//先找到链表的中间节点，再反转他
struct ListNode* cur=head;
while(cur && rmid)//开始遍历这俩个，都不可以为空，为空就结束
{
if(cur->val!=rmid->val)
{
return false;
}
cur=cur->next;
rmid=rmid->next;
}
return true;
}总结：链表做题套路
删除元素得定义prev指针
这个知识点从第一道题目，删除链表元素获取而来
小心malloc的节点，->next的随机值问题，尤其是作为=右值的时候
这个知识点从反转链表的头插那里有点小涉及，但直接报错的是那个划分链表元素，俩次尾插最后连接起来的那个题目，因为那个题目有一个
LessTail->next=GreaterGuard->next;//将俩个链表连接起来
这里等号右值如果不置空的话，很容易出问题
头插的时候，由于头节点的更新，我们的cur往往会被覆盖，这个时候while内部创建next是很有必要的（典型代表：反转链表之头插法）
为了避免空指针被解引用的问题，我们一般在循环中创建next变量
看到求中间节点或者第几个节点或者倒数第几个节点就用快慢指针
对于需要对链表进行操作的，我们除了可以在原先链表中建立指针，我们还可以新开辟一个头节点，使得我们可以进行尾插和头插（尾插不改变元素顺序，头插改变元素顺序）
关于哨兵位带头的问题（要尾删，必建头）
我们必须认识到一个问题：单链表就适合头插头删，不适合尾插尾删
带头对于头插也有好处：这样可以避免重复的更新头节点，很方便嘞！（但是杭哥建议头插不带哨兵头也可以，但是得记得更新）
对于尾插的好处：省略特殊情况的判空
