链舞算法谱---链表经典题剖析

前言:探究链表算法的奥秘,解锁编程新世界!

  欢迎来到我的链表算法博客,这将是您深入了解链表算法,提升编程技能的绝佳机会。链表作为数据结构的重要成员之一,其动态性和灵活性在实现某些功能上发挥不可替代的功效。

本篇博客致力于揭秘链表算法的奥妙,分享实用的学习经验,仅供个人参考。我也希望您能独立实现代码完成相关的题型,还要尝试一题多解,发散思维。

如果对您有帮助,希望您能点赞关注作者,作者会持续输出新鲜干货,尽请期待!

前面,我们学习单链表的基本实现,比如链表的创建,销毁,增删查改等。

如果您不是很了解单链表的相关操作,可以读一下鄙人的单链表博客,或者自行学习。

数据结构篇其二---单链表(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等,敬请期待。

好了作者要休息,感谢您的观看。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/321955.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Android广播机制简介

文章目录 Android广播机制简介广播的基本概念广播的类型广播的使用场景Android广播的优缺点优点缺点 使用Android广播的一些最佳实践: Android广播机制简介 Android广播是一种轻量级的消息传递机制&#xff0c;用于应用程序之间或系统与应用程序之间进行通信。它类似于订阅-发…

缓存淘汰算法中的LRU(Least Recently Used)算法

缓存淘汰算法中&#xff0c;LRU&#xff08;Least Recently Used&#xff09;算法是一种常见的算法。它的基本思想是根据最近的访问情况来决定哪些数据被保留在缓存中&#xff0c;哪些数据被淘汰出去。 具体来说&#xff0c;当需要从缓存中淘汰数据时&#xff0c;LRU算法会选择…

OpenAI 高管:一年后,你会觉得现在的 ChatGPT 像笑话一样糟糕|TodayAI

OpenAI 的首席运营官 Brad Lightcap 表示&#xff0c;一年后&#xff0c;你会觉得现在的 ChatGPT 像笑话一样糟糕。未来的 ChatGPT 版本将会有重大升级。他还讨论了 AI 取代人类工作和对电网的压力的可能性。 虽然我们不知道 OpenAI 何时会推出 GPT-5&#xff0c;但公司高管已…

【小黑送书—第二十期】>>K邻算法:在风险传导中的创新应用与实践价值(文末送书)

01 前言 在当今工业领域&#xff0c;图思维方式与图数据技术的应用日益广泛&#xff0c;成为图数据探索、挖掘与应用的坚实基础。本文旨在分享嬴图团队在算法实践应用中的宝贵经验与深刻思考&#xff0c;不仅促进业界爱好者之间的交流&#xff0c;更期望从技术层面为企业在图数…

ADOP带你了解:长距离 PoE 交换机

您是否知道当今的企业需要的网络连接超出了传统交换机所能容纳的长度&#xff1f;这就是我们在长距离 PoE 交换机方面的专业化变得重要的地方。我们了解扩展网络覆盖范围的挑战&#xff0c;无论是在广阔的园区还是在多栋建筑之间。使用这些可靠的交换机&#xff0c;我们不仅可以…

二叉树的基础遍历2.0

1.0入口&#xff1a;二叉树的基础遍历-CSDN博客 在1.0中使用的是简单的结构体建树&#xff0c;本文注重用二维vector建树。 前序&#xff0c;中序和后序的分析1.0已给出&#xff0c;本文不做过多介绍&#xff0c;本文重点讲二叉树的层序遍历。 先奉上前中后序的代码&#xf…

算法提高之能量项链

算法提高之能量项链 核心思想&#xff1a;区间dp 通过观察发现可以将n个珠子最后的n1个数看作石子 合并石子 在l~r的范围内 找k作隔断 #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N 110,M N<<…

VMware导入ova/ovf虚拟机文件

1.文件-打开-ova文件 2.为新虚拟机起名称 3.等待导入 4.导入完成&#xff0c;可以开始使用 参考链接&#xff1a;VMware导入ova/ovf虚拟机文件

中国家装水管十大品牌排行榜:联塑、日丰、金牛、美尔固、弗锐德等品牌上榜

水管作为家居装修中至关重要的一环&#xff0c;其质量直接关系到我们日常生活的安全和舒适。面对市场上琳琅满目的家装水管品牌&#xff0c;选择一款质量可靠、性能优越的产品成为了许多家庭装修的重要课题。为了助你选购时不踩坑&#xff0c;下面就为大家介绍一下中国家装水管…

vue2 Avoided redundant navigation to current location

再次点击同一个链接会报错 每次使用 push 方法时带上两个回调函数 this.$router.push({name: item.name}, ()>{}, ()>{}) //第二、第三个参数分别为成功和失败的回调函数重写 Vue-router 原型对象上的 push 函数不行 https://blog.csdn.net/weixin_43615570/article/d…

PPPoE实验新手必备:从0到1的网络配置指南!

5月18日&#xff0c;思科华为初级网工课程&#xff0c;等你免费试听 V&#xff1a;glab-mary 今天带大家学习一下华为PPPoE实验配置 01、实验拓扑 02、实验需求 1.完成PPP封装 2.完成PPP的PAP验证 3.完成PPP的CHAP验证 4.完成R1和R2之间的PPPOE 03、实验步骤 a . PPP封…

实测幻方新出的超强AI大模型,中文能力对比GPT4.0不落下风

目前从网上的消息来看&#xff0c;DeepSeek中文综合能力&#xff08;AlignBench&#xff09;开源模型中最强&#xff0c;与GPT-4-Turbo&#xff0c;文心4.0等闭源模型在评测中处于同一梯队。 话不多说&#xff0c;我们开测&#xff01; 1.首先我们来让他直接来一段逻辑推理【并…

Leaflet在WGS84 Web墨卡托投影与WGS84经纬度投影下空间信息变形问题及修正-以圆为例

目录 前言 一、投影的相关知识 1、经纬度投影 2、Web墨卡托投影 二、经纬度投影下的空间信息展示 1、空间信息展示 2、效果展示 3、经纬度投影下的圆修正 三、Web墨卡托投影下空间信息展示 1、底图引用 2、自定义生成圆 总结 前言 在GIS的知识海洋中&#xff0c;对…

软件杯 深度学习花卉识别 - python 机器视觉 opencv

文章目录 0 前言1 项目背景2 花卉识别的基本原理3 算法实现3.1 预处理3.2 特征提取和选择3.3 分类器设计和决策3.4 卷积神经网络基本原理 4 算法实现4.1 花卉图像数据4.2 模块组成 5 项目执行结果6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &a…

Flask gevent启动报错UnicodeDecodeError

文章目录 环境代码报错Track解决思路 环境 acondana 24.1.2python 3.7.13 32bitflask 2.2.3gevent 21.8.0 代码 port 7236 logging.basicConfig(levellogging.INFO, # 控制台打印的日志级别filename./logs/app.log, # 将日志写入log_new.log文件中filemodea, # 模式&…

可视化实验三 Matplotlib库绘图及时变数据可视化

1.1 任务一 1.1.1 恢复默认配置 #绘图风格&#xff0c;恢复默认配置 plt.rcParams.update(plt.rcParamsDefault)#恢复默认配置 或者 plt.rcdefaults() 1.1.2 汉字和负号的设置 import matplotlib.pyplot as plt plt.rcParams["font.sans-serif"]"SimH…

词袋法TFIDF

Tf-idf⽂本特征提取 TF-IDF的主要思想是&#xff1a;如果某个词或短语在⼀篇⽂章中出现的概率⾼&#xff0c;并且在其他⽂章中很少出现&#xff0c;则认为此词或者短语具有很好的类别区分能⼒&#xff0c;适合⽤来分类。TF-IDF作⽤&#xff1a;⽤以评估⼀字词对于⼀个⽂件集或…

医药垃圾分类管理系统|基于SSM医药垃圾分类管理系统的系统设计与实现(源码+数据库+文档)

医药垃圾分类管理系统 目录 基于SSM医药垃圾分类管理系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1系统登录模块 2管理员模块实现 3用户模块实现 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博…

a-table 控制列的展示和隐藏

一、业务场景&#xff1a; 最近在使用 Antd-vue 组件库的时候&#xff0c;a-table需要根据不同角色的权限显示和隐藏 columns的列 为了避免大家走弯路&#xff0c;为大家整理了一下&#xff0c;粘走可以直接用的那种 二、具体实现步骤&#xff1a; 1.在需要显示与隐藏的列增加一…

相机内存卡格式化怎么恢复?恢复数据的3个方法

相机内存卡格式化后&#xff0c;许多用户都曾面临过照片丢失的困境。这些照片可能具有极高的纪念价值&#xff0c;也可能包含着重要的信息。因此如何有效地恢复这些照片变得至关重要。本文将详细介绍三种实用的恢复方法&#xff0c;帮助您找回那些珍贵的影像。 下面分享几个实…