【数据结构】猛猛干11道链表OJ（未完待续ing）

前言知识点

链表的调试技巧

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指向3free(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了，定义一个Guardstruct 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;//这句是一个大bughead=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，当只有一个节点的时候，会出现空指针的解引用