前言:探究链表算法的奥秘,解锁编程新世界!
欢迎来到我的链表算法博客,这将是您深入了解链表算法,提升编程技能的绝佳机会。链表作为数据结构的重要成员之一,其动态性和灵活性在实现某些功能上发挥不可替代的功效。
本篇博客致力于揭秘链表算法的奥妙,分享实用的学习经验,仅供个人参考。我也希望您能独立实现代码完成相关的题型,还要尝试一题多解,发散思维。
如果对您有帮助,希望您能点赞关注作者,作者会持续输出新鲜干货,尽请期待!
前面,我们学习单链表的基本实现,比如链表的创建,销毁,增删查改等。
如果您不是很了解单链表的相关操作,可以读一下鄙人的单链表博客,或者自行学习。
数据结构篇其二---单链表(C语言+超万字解析)-CSDN博客
我们要注重理论实践结合,阅读他人的代码和相关题解(力扣网站每道题都有大佬(官方)的优秀题解供我们学习),更能熟悉掌握链表的核心知识。
本期精选链表算法的高级话题,选自力扣网站(后面附带刷题链接)。如反转链表,环形链表检测,链表相交,合并有序链表,移除链表元素,分割链表等一系列好题。
编程语言:C语言。
学习方法:
学习数据结构要多画图分析,一步一步来,能积微者速成。
一切条件判断,循环条件不知道怎么写的情况,都是因为图没有画清楚,逻辑没捋清楚。自己动手画比脑补来的快。
目录
前言:探究链表算法的奥秘,解锁编程新世界!
一、反转链表(简单)
思路一:(三指针法)取节点头插。
思路二:(三指针法)直接反转
思路三:(三指针法)思路一的优化版本
二、移除链表元素(简单)
思路一:(双指针法)直接删除值为val的节点。
思路二:创建新链表
三、链表的中间节点(简单)
思路一:计算链表长度确定中间结点
思路二:快慢指针法
四、删除链表的倒数第k个节点(中等)
思路一:快慢指针法
五、返回倒数第k个节点(简单)
六、合并两个有序链表(简单)
思路一:创建新链表尾插
七、链表分割(较难)
思路一: 先分割再合并(简单的思路)
八、链表的回文结构(简单)
思路一:中间节点+反转链表+双指针法
思路二:数组(换种数据结构)+双指针(对撞指针)
九、相交链表(简单)
思路一:暴力遍历。
思路二: (类似)快慢指针
十、环形链表(简单or难?)
思路一:快慢指针法
结尾
一、反转链表(简单)
据说这是面试出镜率最高的链表题。
206. 反转链表 - 力扣(LeetCode)
这里提供了三组示例供我们实际测试代码。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {}
代码通过注释的方式给了我们结构体的声明,接着让我们实现函数内部的逻辑。
先分析函数和返回类型吧。
返回值:struct ListNode* 结构体指针,这里返回反转链表后的头指针。
函数参数:就一个参数,传入源链表的头指针。
下面提供几种思路。
思路一:(三指针法)取节点头插。
链表的元素是节点。我们就有第一种想法,将每个节点一个一个取下来进行头插。
同时考虑多种情况不符合人脑逻辑,我们先考虑第一种示例,再完善整体的逻辑。
怎么做呢?先分析已知指针的指向。
只有一个头指针指向链表的第一个节点。我们要实现把节点依次取下来进行头插的操作。显然只有头指针是不够的,我们再创建节点(结构体)指针 。
那么创建几个结构体指针呢?
首先,我们处理链表问题,不会轻易动用头指针,除非链表的第一个节点改变了,才需要改变头指针指向。
所以要第一个头指针prev。如下图:
这样有了prev也指向第一个节点,就不要动head指针遍历链表了。
那么如何一个节点指针够了吗?
还是回归到问题上,我们要取下每个节点进行头插。
请阅读下面的代码和观察下面的图
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = head;//prev指向head指向的节点,即第一个节点。prev->next = NULL;//将结点指针指向的节点的指针域置空,意味着把节点取下来了。
}
很遗憾只通过prev指针把第一个节点取下来了,但是第二个节点的位置找不到了。起不到头插的作用。
所以还需要个next的节点指针,指向取下节点的下一个节点。
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = head;//prev指向head指向的节点,即第一个节点。struct ListNode* next = head;//next也指向第一个节点。next = prev->next;//先让next指向下一个节点。prev->next = NULL;//将结点指针指向的节点的指针域置空,意味着把节点取下来了。
}
取第二个节点的情况
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = head;//prev指向head指向的节点,即第一个节点。struct ListNode* next = head;//next也指向第一个节点。next = prev->next;//先让next指向下一个节点。prev->next = NULL;//将结点指针指向的节点的指针域置空,意味着把节点取下来了。//取第二个节点prev = next;//先让prev指向原链表的第二个节点。next = prev->next;//代码同取下第一个节点的情况。prev->next = NULL;//执行头插操作prev->next = head;//连接第一个节点head = prev;//头插改变头指针的指向。}
那么后面规律自然清晰可寻了,我们这里考虑结束的情况。
选择什么循环和循环条件是什么问题就迎刃而解了。
按照前面的逻辑
prev跟上next,即prev=next;
next指向原先链表尾结点的指针指向部分,即next=NULL;
连接节点,prev->next=head;
再调整头指针的指向,即head=prev;
最终结果出来了,这个时候的head和prev指向新链表(反转链表)的第一个节点。next指向空,可作为循环条件。
最终结果如图:
代码就可以写了
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = head;//prev指向head指向的节点,即第一个节点。struct ListNode* next = head;//next也指向第一个节点。next = prev->next;//先让next指向下一个节点。prev->next = NULL;//将结点指针指向的节点的指针域置空,意味着把节点取下来了。while (next){ //取第二个及之后的节点prev = next;next = prev->next;prev->next = NULL;//头插prev->next = head;head = prev;}return head;}
提交一下。
挫折才是算法题的常态,不急看看红字说什么。
原来是空链表的情况啊 。也就是题目所给示例3的情况。
最前面直接加个if判断就行了,空链表直接让他返回空指针就🆗了。
最终代码实现
struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;struct ListNode* prev = head;//prev指向head指向的节点,即第一个节点。struct ListNode* next = head;//next也指向第一个节点。next = prev->next;//先让next指向下一个节点。prev->next = NULL;//将结点指针指向的节点的指针域置空,意味着把节点取下来了。while (next){prev = next;next = prev->next;prev->next = NULL;prev->next = head;head = prev;}return head;}
用时方面击败了100%的人,鼓励自己一下。
由于代码已经通过了,示例二我就不多说了,需要请您自行梳理。
思路二:(三指针法)直接反转
直接改变指向如何实现呢?
三指针。三个指针能改变朝向,双指针只能改变一次,不能循环起来。
第一步:
断开节点1和节点2,节点一指向n1;
第二步:
按顺序n1指向n2,n2指向n3,n3指向下一个节点 (n3->next);
接下来判断循环结束条件。
需要注意一次只改变一个节点的指针部分的指向。节点1和节点2只是断开了,节点1指向了空,并没有让节点2指向节点1。
循环结束条件为n2为NULL。
需要注意在连接最后一个节点时,n3已经为空指针了,不能再往后挪,即n3=n3->next;
补充:->结构体指针访问操作符,本质是指针解引用访问结构体的成员。而空指针不能解引用,会报错。
最后前面写个if语句,如果是空链表直接返回NULL。
struct ListNode* reverseList(struct ListNode* head) {if (NULL == head)//空链表return NULL;struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = n2->next;while (n2){n2->next = n1;n1 = n2; n2 = n3;if (n3)//尾结点改变连接朝向,n3已经为NULL,不能再解引用。n3 = n3->next;}return n2;
}
思路三:(三指针法)思路一的优化版本
思路一要修改原先的head,虽然和思路一思想一样,但重新创建一个新头指针,创建一个新链表,可读性好一些。
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newhead = NULL;//定义新的头指针。while (cur){struct ListNode* next = cur->next;//循环内部创建不用额外判断空链表的情况。cur->next = newhead;newhead = cur;cur = next;}return newhead;}
二、移除链表元素(简单)
203. 移除链表元素 - 力扣(LeetCode)
本题还是给了三组测试用例,我们先从第一组开始分析。
第一组样例:
思路一:(双指针法)直接删除值为val的节点。
要做到直接删除,至少要用两个相邻指针做到。
prev->next=pcur->next;//指向值为val的下一个节点
pcur=prev->next;//pcur指向
结束条件:
这里可用pcur作为循环结束的条件。
看不明白请自行画图分析。
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* prev = NULL;struct ListNode* pcur = head;while (pcur){if (pcur->val == val)//当前pcur所在节点值为val,执行删除{prev->next = pcur->next;free(pcur);pcur = prev->next;}else//pcur指向节点值不为val,prev,pcur整体往下一个节点走。保证它俩紧挨着。{prev = pcur;pcur = pcur->next;}}return head;//返回头指针}
接下来第二组和第三组测试用例
第二组给了空链表的示例,由于直接最前方写个if分支直接return NULL;
if (NULL == head)return NULL;
第三组测试用例:
由于第一个节点就符合条件,而此时prev还为NULL,prev->next的行为会报错。
这种情况就要用单链表头插的思路,即head和pcur实现了
这种全符合 val的情形,只有head和pcur在动,没prev什么事了。
🆗,总结一下先判断要不要进行头删,直到第一个节点不在删除就得动用prev和pcur来进行一般的删除(第一组用例的方法)。
综合一下三组用例:最终代码实现
struct ListNode* removeElements(struct ListNode* head, int val) {//空链表直接返回。if (NULL == head)return NULL;struct ListNode* prev = NULL;struct ListNode* pcur = head;//判断要不要头删。while (pcur->val == val&&pcur!=NULL){head = pcur->next;free(pcur);pcur = head;if (pcur == NULL)//如果全是val的情况,全部执行头删,pcur将为空,判断一下{return NULL;}}//第一个节点不是val启动prev,pcur,遍历链表进行删除。while (pcur){if (pcur->val == val)//当前pcur所在节点值为val,执行删除{prev->next = pcur->next;free(pcur);pcur = prev->next;}else//pcur指向节点值不为val,prev,pcur整体往下一个节点走。保证它俩紧挨着。{prev = pcur;pcur = pcur->next;}}return head;//返回头指针 }
看来情况考虑全了。
下面提供另一种思路:
思路二:创建新链表
虽然说是创建新链表,实际并没有增加新的节点。
一个新链表(单链表)有头有尾。
//创建新链表struct ListNode* newhead = NULL;struct ListNode* newtail = NULL;
接下来我们要遍历原链表,找到值不为val的节点取下来进行尾插。
struct ListNode* pcur = head;//引入一个指针变量,遍历整个链表
第一步:
由于第一个节点val值为1,取下来。
newhead = pcur;newtail = pcur;
第二步:
pcur向后遍历,且让取下来的第一个节点指向空。因为单链表最后一个节点必须指向空,不然会出问题。
pcur = pcur->next;//往下继续遍历。 newtail->next=NULL;//新链表尾指针指向空
第三步:
由于第二个节点val值为2,也取下来。看下图
newtail->next = pcur;newtail = newtail->next;
第四步:
pcur继续向后遍历,且让取下来的第二个节点指向空。结合上图分析。
pcur=pcur->next; newtail->next=NULL;
到这里规律就很明显了。
首先是pcur遍历原链表,pcur指向原链表的空指针说明循环结束。
pcur->val不满足指定val就尾插到新链表,此时又分两种情况,即第一次插入和后面的插入。第一次插入要修改头指针,使头指针指向第一个节点。后面进行尾插,只需要后一个节点连接前一个节点,并移动尾指针即可。
然后,若pcur->val满足指定val,就释放该节点,继续往后遍历。
需要注意的是,将节点取下来只是个形象的说法,本质就是新链表的头尾指针指向原先的节点。每次满足条件的节点取下来其指针部分指向要改为空。
如果觉得文字看不明白的话
请您自己画图配合看一下下面的代码吧。
struct ListNode* removeElements(struct ListNode* head, int val) {//该代码逻辑上包含了空链表,不用单独判断了。struct ListNode* newhead = NULL;struct ListNode* newtail = NULL;struct ListNode* pcur = head;while (pcur)//遍历原链表{if (pcur->val != val)//不满足指定val{if (NULL == newtail)//新链表第一次插入节点{newhead = pcur;newtail = pcur;}else//后面的插入,和单链表尾插相同的思路{newtail->next = pcur;//连接前一个节点newtail = newtail->next;//改变尾指针的指向}pcur = pcur->next;//往下继续遍历。newtail->next = NULL;//尾指针指向空,保证新链表(单链表)不出错}else{struct ListNode* del = pcur;//临时指针存储满足值为val的节点pcur = pcur->next;//继续遍历free(del);//释放满足条件的节点}}return newhead; }
三、链表的中间节点(简单)
876. 链表的中间结点 - 力扣(LeetCode)
思路一:计算链表长度确定中间结点
这种思路很简单,引入int len;先遍历链表计算链表的长度,再遍历找到中间节点并打印。
链表的长度是节点的个数。
把链表元素(节点)想象成数组元素下标的形式
比如下面是奇数个节点就是 ,链表长度为5,中间长度就是5/2==2(整数除法)。就是对应下标为2的节点,就是3.
对于链表长度是偶数,节点个数是偶数的情况呢。
这里链表长度是6,中间长度是6/2=3,对应下标为三的节点,是4。符合题意。
int k = len / 2;就是中间长度了。
struct ListNode* middleNode(struct ListNode* head){if (head == NULL)//空链表return head;int len = 0;//长度变量struct ListNode* pcur = head;while (pcur)//遍历求链表长度{pcur = pcur->next;len++;}pcur = head;//重置pcurint k = len / 2 ;//中间结点到起点的长度。while (k--){pcur = pcur->next;}return pcur;//返回中间节点的指针}
思路二:快慢指针法
思路一方法很好理解,但由于要计算长度,终归要先遍历一遍数组。然后找中间节点,相当于又遍历了一遍。
下面介绍快慢指针法
快慢指针,广泛应用于大量的算法场景。
先介绍背景,这种方法在解决此题时,不用求链表长度,只需遍历一遍。
快慢指针
以单链表为背景
快慢指针指的是移动步长,正如名称所示,快指针走的快(单次走的步数多),慢指针走得慢(单次走的少)
什么又叫走的步数多和走的步数少呢?
先说快慢指针的定义
struct ListNode {int val;struct ListNode *next; };
struct ListNode* fast = head;struct ListNode* slow = head;
快慢指针这里是结构体变量,很显然 fast和fast->next类型一样,可以进行赋值操作。
那么fast->next->next呢?也是结构体指针类型。
好像明白了!
fast=fast->next;//走一步。
fast=fast->next->next;//走两步。
同一循环下,慢指针走一步,快指针走两步。快指针到终点,结束循环,慢指针才走到链表的一半,就是中间节点处。
实践开始:
先考虑题中给的第一组示例。
struct ListNode* middleNode(struct ListNode* head)
{if (head == NULL){return NULL;//空链表可用不上快慢指针,直接返回空即可}//定义快慢指针struct ListNode* fast = head;struct ListNode* slow = head;while (fast->next){slow = slow->next;//慢走一fast = fast->next->next;//快走二}return slow;//慢指针所指向的就是中间节点
}
做到这儿大多人已经迫不及待地提交了。
只过了一个测试用例,太惨了。观察一下上面的图,题目中给定的测试用例二我们还没测呢。
偶数情况下的循环结束条件是fast==NULL;
慢指针依旧指向中间节点。
struct ListNode* middleNode(struct ListNode* head) {if (head == NULL){return NULL;//空链表可用不上快慢指针,直接返回空即可}//定义快慢指针struct ListNode* fast = head;struct ListNode* slow = head;while (fast->next && fast)//补上偶数的情况{slow = slow->next;//慢走一fast = fast->next->next;//快走二}return slow;//慢指针所指向的就是中间节点 }
然后提交。
呃?怎么还是报错了,明明逻辑没有错啊?
好吧还是错了,问题肯定出在修改过的地方。
while (fast->next && fast)
逻辑与是从左向右计算表达式的结果的。若fast已经为NULL,它会先进行左边的判断fast->next,显然会报错。应该先判断fast是不是NULL,在判断fast->next。
while ( fast && fast->next )
struct ListNode* middleNode(struct ListNode* head) {if (head == NULL){return NULL;//空链表可用不上快慢指针,直接返回空即可}//定义快慢指针struct ListNode* fast = head;struct ListNode* slow = head;while (fast && fast->next)//奇数个节点和偶数个节点的情况{slow = slow->next;//慢走一fast = fast->next->next;//快走二}return slow;//慢指针所指向的就是中间节点 }
🆗,思路二及原理讲解和可能遇到的问题就解决了。
四、删除链表的倒数第k个节点(中等)
19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
思路一:快慢指针法
此题和链表的中间节点都可采用快慢指针法,只不过用快慢指针的方式不同。
快慢指针不一定比谁走得快,而可以认为谁走得远。
slow负责找倒数第k个节点,fast领先slow结束循环。
这里可以看到fast比slow多走了一步,可以用fast->next作为结束循环的条件。
那么这里有普遍的规律吗?
找倒数第二个节点,fast比slow多走一步。
找倒数第三个节点,fast同样指向尾结点,此时fast比slow多走两步。
找倒数第一个节点,fast同样指向尾结点,此时fast和slow相差0步
原来如此,找倒数第k个节点,fast要先走k-1步,然后再和slow一起走,符合快慢指针。
这里要执行删除操作,我们在定义一个prev指针循环找slow指向的前一个结点。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {if (NULL == head)return NULL;struct ListNode* fast = head;struct ListNode* slow = head;int k = n-1 ;while (k--)//fast先走n-1步{fast = fast->next;}while (fast->next)//同时走{fast = fast->next;slow = slow->next;}struct ListNode* prev = head;//定义prev指针找slow的前一个结点。while (prev->next != slow)//找……ing{prev = prev->next;}//执行删除操作prev->next = slow->next;free(slow);//返回头指针。return head;}
只过了一个测试用例?嗯冷静!
根据链表节点删除的经验,这种情况十有八九没考虑头删的情况。
下面分析一下不满足的测试样例。
struct ListNode* prev = head;//定义prev指针找slow的前一个结点。while (prev->next != slow)//找……ing{prev = prev->next;}
明白了,这个时候prev和slow一样,要删掉头节点,这个循环不包括头删的情况。
那么用if_else语句分开讨论吧。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {if (NULL == head)return NULL;struct ListNode* fast = head;struct ListNode* slow = head;int k = n-1 ;while (k--){fast = fast->next;}while (fast->next){fast = fast->next;slow = slow->next;}//判断头删还是非头删的情况if (slow == head){head = head->next;//修改头指针的指向即可。}else {struct ListNode* prev = head;//定义prev指针找slow的前一个结点。while (prev->next != slow)//找ing{prev = prev->next;}//执行删除操作prev->next = slow->next;free(slow);}//返回头指针。return head;}
时间上打败了全世界的人,加油!
总结
1.执行链表删除时考虑头删的情况。
2.考虑空链表的情况。
3.熟练快慢指针在此题的应用。
4.不用像作者那样试错,自己考虑完所有情况(画图分析),一遍过就完事。
遗漏的地方自己要独立分析完成。
五、返回倒数第k个节点(简单)
面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode)
本题作为四题快慢指针的补充。
四题有过这幅图
下面我给出另一张图,分析一下区别。
结论就是循环条件不同,前者以fast->next==NULL结束,后者以fast==NULL,结束。
还有一个区别:前者fast比slow先走k-1步,后者fast先走k步。
🆗,我们用后者的形式快速解决这道题。
int kthToLast(struct ListNode* head, int k) {if (head == NULL)//空链表踢出跑步比赛资格{return NULL;}struct ListNode* fast = head;struct ListNode* slow = head;while (k--)//fast先行k步{fast = fast->next;}while (fast)//fast和slow同时走,注意此时结束条件{fast = fast->next;slow = slow->next;}return slow->val;//返回倒数第k个节点的val值 }
be far ahead
写得最快的一题。
六、合并两个有序链表(简单)
据说这是面试出镜率第二高的面试题。
21. 合并两个有序链表 - 力扣(LeetCode)
leetcode给的函数原型。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {}
函数参数是两个链表的头指针,返回合并后链表的头指针。
思路一:创建新链表尾插
不需要复杂的套路,只要给我一个新链表的头指针和尾指针,我就能解决这道题。
由于目的是合并成升序表,原先的两个链表的节点两两对应比较,选择小的尾插,对应指针往后走一位。
如果是第一次尾插,需要注意newhead。
原先两个链表总有一个先走完;
再将剩下一个链表后面的节点相连即可。
nie
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//其中一个表为空表,合并结果就是另外一个表(无论其是否是空表)if (list1 == NULL)return list2;if (list2 == NULL){return list1;}//创建新链表的头尾指针struct ListNode* newhead = NULL;struct ListNode* newtail = NULL;//循环结束条件,任一链表被排布完全。while (list1 && list2){if (list1->val < list2->val)//比较两个有序链表各自当前节点大小{if (newtail == NULL)//第一次尾插{newhead = list1;newtail = list1;}else//后续的尾插{newtail->next = list1;newtail = newtail->next;}list1 = list1->next;newtail->next = NULL;}else{if (newtail == NULL)//第一次尾插{newhead = list2;newtail = list2;}else//后续尾插{newtail->next = list2;newtail = newtail->next;}list2 = list2->next;newtail->next = NULL;}}//尾指针直接连接剩下没填完链表的节点if (list1 != NULL){newtail->next = list1;}if (list2 != NULL){newtail->next = list2;}return newhead;//返回新链表的头指针。}
七、链表分割(较难)
链表分割_牛客题霸_牛客网 (nowcoder.com)
思路一: 先分割再合并(简单的思路)
本题难点在于不能改变原来的数据顺序。
这里没给测试用例,我们这里假设原链表为{3 ,4,6,1,4,5,2,8},其中x为4。
那么按照题意将小于x和大于等于x的分割在两边。
3,1,2 4,6,4,5,8
注意顺序不能变。
其实上面已经给定了思路。就是将原链表分割成两个链表,再将两个链表的尾和头连接起来。
这里为了方便,先将哨兵位(头节点)的概念,因为我单链表没涉及哨兵位的东西,所以这里默认大家不知道的情况。
有时候,为了方便,我们会在第一个节点前附带一个节点,称这个节点为头节点(哨兵位)。
这里我们可以重新定义空链表了。
原先我们认为空链表不带任何节点,其实这句话是针对不带头节点的链表。
由于头节点的数据域不会存储有效的数据(有效情况可以利用这个存储比如链表的长度什么的),指针域会存储NULL(针对空表)。
那么广泛的空表可以认为没有任何有效数据的节点。
这里头指针不在指向第一个节点,而是指向头节点(哨兵位)。
头节点和第一个节点是不一样的东西(虽然文字上相同),这里把头节点称为哨兵位更合适,不易混淆。
为什么要介绍哨兵位的概念?
至少我们了解一点,再进行尾插和头插相关插入数据的操作时,如果是不带哨兵位的空链表,那么最初头指针指向NULL,这种就要分情况讨论(第一次插入和第二次插入)。而带哨兵为的单链表,至少有一个节点,像桥梁一样,方便我们进行尾插头插,而不用这么麻烦。
链表分割完了吗,还没有,必须确保每个节点的下一个指向。
由题意,我们要尾首连接这个两个链表 。
lesstail->next=greaterhead->next;
确保尾指针指向空
greatertail->next=NULL;
由于创建了两个哨兵位,我们最好销毁哨兵位。
先把头指针指向改了:
pHead=lesshead;
释放哨兵位:
free(lesshead);
free(greaterhead);
下面开始写代码吧
此题牛客网不提供C语言的方式,我们就选择C++完成此题,因为C++兼容C.
class Partition { public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lesshead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* lesstail = lesshead;struct ListNode* greaterhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* greatertail = greaterhead;struct ListNode* pcur = pHead;//链表分割while (pcur){if (pcur->val < x){lesstail->next = pcur;lesstail = lesstail->next;}else{greatertail->next = pcur;greatertail = greatertail->next;}pcur = pcur->next;}//两个链表的连接和尾部置空lesstail->next = greaterhead->next;greatertail->next = NULL;pHead = lesshead->next;free(lesshead);free(greaterhead);return pHead;} };
八、链表的回文结构(简单)
234. 回文链表 - 力扣(LeetCode)
先分享我一开始的愚蠢想法。
哎,这不简单嘛?搞两个对撞指针不就行了吗。
一个从头,另一个从尾部开始。
然后我才意识道单链表的单向性。不过并没无功,开始尝试就已经迈向了成功。
思路一:中间节点+反转链表+双指针法
正如小标题所说,我们要借助先前的题的函数了
一、反转链表
struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;struct ListNode* prev = head;//prev指向head指向的节点,即第一个节点。struct ListNode* next = head;//next也指向第一个节点。next = prev->next;//先让next指向下一个节点。prev->next = NULL;//将结点指针指向的节点的指针域置空,意味着把节点取下来了。while (next){prev = next;next = prev->next;prev->next = NULL;prev->next = head;head = prev;}return head;}
三、链表的中间节点
struct ListNode* middleNode(struct ListNode* head) {if (head == NULL)//空链表return head;int len = 0;//长度变量struct ListNode* pcur = head;while (pcur)//遍历求链表长度{pcur = pcur->next;len++;}pcur = head;//重置pcurint k = len / 2;//中间结点到起点的长度。while (k--){pcur = pcur->next;}return pcur;//返回中间节点的指针 }
需要注意反转链表的函数再反转链表后,尾指针会指向空。 如下图所示
找中间节点的函数只会返回中间节点的指针。
这里可用迭代过程中,可用rightpcur==NULL终止这一过程。
struct ListNode* middleNode(struct ListNode* head)
{if (head == NULL)//空链表return head;int len = 0;//长度变量struct ListNode* pcur = head;while (pcur)//遍历求链表长度{pcur = pcur->next;len++;}pcur = head;//重置pcurint k = len / 2;//中间结点到起点的长度。while (k--){pcur = pcur->next;}return pcur;//返回中间节点的指针
}struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;struct ListNode* prev = head;//prev指向head指向的节点,即第一个节点。struct ListNode* next = head;//next也指向第一个节点。next = prev->next;//先让next指向下一个节点。prev->next = NULL;//将结点指针指向的节点的指针域置空,意味着把节点取下来了。while (next){prev = next;next = prev->next;prev->next = NULL;prev->next = head;head = prev;}return head;}
bool isPalindrome(struct ListNode* head) {struct ListNode* midhead = middleNode(head);struct ListNode* rightpcur = reverseList(midhead);struct ListNode* leftpcur = head;while (rightpcur){if (rightpcur->val != leftpcur->val){return false;}else{rightpcur = rightpcur->next;leftpcur = leftpcur->next;}}return true;
}
思路二:数组(换种数据结构)+双指针(对撞指针)
此题本质是判断会不会回文的问题。既然单链表数据结构不好判断。
我们就把单链表数据,拷贝一份放到数组上。
类似动态顺序表的写法,创建动态数组。
bool isPalindrome(struct ListNode* head) {int* arr = (int*)malloc(sizeof(int) * 4);//函数内部手动创建一个动态顺序表int size = 0;//当前有效数据int capacity = 4;//数据容量大小struct ListNode* pcur = head;while (pcur)//将单链表的数据拷贝到动态内存。{if (size == capacity)//看情况扩容{int newcapacity =2 * capacity;arr = (int*)realloc(arr, newcapacity*sizeof(int));capacity = newcapacity;}arr[size++] = pcur->val;pcur = pcur->next;}//动态数组下标当作指针使用int left = 0;//有效数据的左下标int right =size - 1 ;//有效数据的右下标while (left <= right){if (arr[left] != arr[right])return false;//有一个对应位数据不等就不是回文。left++;right--;}return true;//都符合,是回文结构。
}
动态还要考虑扩容和节省空间,干脆不要空间了,节约时间,用静态顺序表吧。
bool isPalindrome(struct ListNode* head) {int arr[100000];//一次性开辟大的空间,刚好符合题目最大的数据个数int size = 0;//当前有效数据struct ListNode* pcur = head;while (pcur)//将单链表的数据拷贝到定长数组上{arr[size++] = pcur->val;pcur = pcur->next;}//定长数组下标当作指针使用int left = 0;//有效数据的左下标int right =size - 1 ;//有效数据的右下标while (left <= right){if (arr[left] != arr[right])return false;//有一个对应位数据不等就不是回文。left++;right--;}return true;//都符合,是回文结构。 }
九、相交链表(简单)
160. 相交链表 - 力扣(LeetCode)
解决这道题分两步:
1.判断链表是否相交。
2.若相交返回交点节点的指针,否则返回NULL。
那怎么判断链表相不相交呢?
图中所给示例即为链表相交的情况。
链表不相交如图。
链表不相交和链表相交有什么能够显著的区别?
你说相交有交点,不相交没有交点呗。
有道理,但我们先判断是否相交,再确认交点是谁。
很明显,如果我们同时遍历两个链表,相交链表的尾结点是一样的,不相交的链表的尾结点不一样。
总结一下:判断相交即判断尾结点相等。
下面提供两种思路
思路一:暴力遍历。
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {if (headA == NULL && headB == NULL){return NULL;}struct ListNode* pcur1 = headA;struct ListNode* pcur2 = headB;while (pcur1->next){pcur1 = pcur1->next;}while (pcur2->next){pcur2 = pcur2->next;}if (pcur2 != pcur1)//判断两个单链表尾结点是否相等。return NULL;pcur1 = headA;pcur2 = headB;//暴力查找while (pcur1)//嵌套while循环,A链表和B链表的所有节点一一比较。{pcur2 = headB;while (pcur2){if (pcur2 == pcur1){return pcur2;}pcur2 = pcur2->next;}pcur1 = pcur1->next;}//置空pcur1 = NULL;pcur2 = NULL;//找不到就返回空。return NULL;
}
其实这么些不用判断相不相交,我都暴力查找了。
时间复杂度o(n*n) 或o(n*m),删掉前面两个while循环也可,但是杯水车薪,稍微节约点时间。
思路二: (类似)快慢指针
还是这张图
我们其实可以一眼看到这叫交点就是C1,要是这两个链表一样长就好了,这样同时走,第一次节点地址相同就确定交点了,可惜这不是一样长的链表。
先不要叹气,思路不就有了吗?
我们模拟成等长链表不就行了吗。
链表有长有短,定义两个指针指向各自的头节点,让长的链表指针先走,走到等长的位置,然后两个指针同时走就行了啊。这种是不是和四、五题的快慢指针有异曲同工之妙。
整理一下思路
1.判断是否相交。
2.计算链表的长度差。
3.判断哪个是长链表。
4.定义双指针,长链表先走,然后同时走,第一次相遇即交点。
开始写代码。
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {//判断空链表,任一一个为空必然不相交,虽然题目条件不包括空链表的情况。if (headA == NULL && headB == NULL)return NULL;struct ListNode* pcur1 = headA, * pcur2 = headB;int lenA = 1, lenB = 1;//记录长度变量//找尾结点,并计算长度while (pcur1->next){pcur1 = pcur1->next;lenA++;}while (pcur2->next){pcur2 = pcur2->next;lenB++;}if (pcur1 != pcur2){return NULL;}int gap = abs(lenA - lenB);//abs为整型的绝对值函数,计算长度差距struct ListNode* fastlist = headA;//快指针struct ListNode* slowlist = headB;//慢指针//假设不成立if (lenA < lenB){fastlist = headB;slowlist = headA;}//快指针先走gap步。while (gap--){fastlist = fastlist->next;}//同时走while (fastlist){fastlist = fastlist->next;slowlist = slowlist->next;if (fastlist == slowlist){return fastlist;}}//为了防止不返回值,假装在这里返回空指针。//上面逻辑上肯定能返回值,非要搁这儿报错,只能在最后补上了。return NULL; }
这道题搞定了。
时间复杂度o(n).
十、环形链表(简单or难?)
141. 环形链表 - 力扣(LeetCode)
先说一下循环链表的概念, 前面的单链表称作单向不循环链表,不循环是什么意思呢?
单链表的尾结点指向NULL,即不循环。那么循环链表的概念就可以说,尾结点的下一个指针指向头节点的链表称为循环链表,如上图的示例一
而这里的示例一不难发现,尾结点的指针部分指向的是第二个节点,这就是一般的环形链表了。
下面我们关注此题如何解决?
很容易发现我们过去的迭代思路用不了了,因为对于在环形链表中循环,像之前那样写(如下代码),陷入死循环了。
while (pcur) {pcur = pcur->next; }
那具体怎么解决呢?判断走过一个节点两次?
好像不现实!再想想环形结构有什么特点。
环形结构是个圈吧。怎样判断自己的运动轨迹是圈?
在操场跑步的两个人,如果速度不一样,两个人一直跑,早晚会出现套圈的情况。而出现套圈这一情景,不就说明了操场的结构是环状结构吗。
对比在程序中,速度不一的两个人,不就是快慢指针吗?
快指针一次走两步,慢指针一次走一步。快指针先进环,慢指针后进环。两者出现相遇(套圈)就证明这是环状结构。
下面提供本题作者的唯一思路。其它方法自行搜leetcode题解
思路一:快慢指针法
bool hasCycle(struct ListNode* head) {if (head == NULL)//空链表取消比赛资格return false;struct ListNode* fast = head, * slow = head;//定义快慢指针while (fast)//若循环能结束,就说明非环状链表。{fast = fast->next->next;//快走二slow = slow->next;//慢走一if (fast == slow)//若是环状结构,快慢指针必向重逢。{return true;}}//非循环链表的情况。return false;
}
怎么又出错了,估计又出现空指针解引用的问题。
bool hasCycle(struct ListNode* head) {struct ListNode* fast = head, * slow = head;//定义快慢指针if (head == NULL)//空链表return false;while (fast&&fast->next)//若循环能结束,就说明非环状链表。{fast = fast->next->next;//快走二slow = slow->next;//慢走一if (fast == slow)//若是环状结构,快慢指针必向重逢。{return true;}}//非循环链表的情况。return false;
}
结尾
鉴于笔者写到这里神志不清了,影响创作质量,于是分期写完单链表的练习。
给您总结一下相关方法:
1.快慢指针法(双指针)
2.双指针和三指针。
3.弗洛伊德判环法(环形链表)//感兴趣可以自行了解。
转化思想,将复杂问题转化成曾经解决的问题或者易上手的问题。
下期更有极高价值的题,比如约瑟夫,环形链表II等,敬请期待。
好了作者要休息,感谢您的观看。