【LeetCode题目详解】(三)21.合并两个有序链表、141.环形链表、142.环形链表Ⅱ
创始人
2024-04-25 11:57:01
0

目录

一、力扣第21题:合并两个有序链表

解法思路

代码一

代码二

代码三

二、力扣第141题:环形链表

1.快慢指针法

2.证明快慢指针是可行的

三、力扣第142题:环形链表Ⅱ

1.解题思路

2.代码

总结


一、力扣第21题:合并两个有序链表

题目链接:21. 合并两个有序链表 - 力扣(Leetcode)

题目描述:

 

解法思路

对于这个题目而言,我们肯定是很熟悉的,因为我们已经讲解过一个合并两个有序数组的题目了。这道题完全只是将数组改成了链表。那么我们在链表中使用的方法是尾插法。谁小先插谁

我们先过一遍思路吧,首先我们先看这个图

我们的思路是这样的,先创建两个指针,newHead和tail,用于记录最后返回的链表的头和尾,我们让他们一开始指向NULL

 然后我们看如果list1->valval时,我们就让newHead和tail都指向list1,然后tail向后走一步,list向后走一步,反之则移动执行另外一个链表的操作,如下图所示

 然后我们一直循环下去

 

 

 

 当只要有一个链表为空以后,那么直接将两个链表链接起来即可

 

 这就是我们的大体思路,但是需要注意的是,有可能一开始会有其中一个链表是空链表,那么这种我们可以一开始做一个判断,只要有一个为空,返回另外一个链表即可

代码一

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/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* tail=NULL;//只要两个都不是空链表那么就可以继续执行下去while(list1 && list2){//1的值小于2的值时if(list1->valval){//链表头为空,这是第一次插入,需要特殊处理if(newHead==NULL){newHead=tail=list1;list1=list1->next;}//正常情况处理else{tail->next=list1;list1=list1->next;tail=tail->next;}}//1的值大于等于2的值时else{//链表头为空,是第一次插入,需要特殊处理if(newHead==NULL){newHead=tail=list2;list2=list2->next;}//正常情况处理else{tail->next=list2;tail=tail->next;list2=list2->next;}}}if(list1==NULL){tail->next=list2;}else{tail->next=list1;}return newHead;
}

运行结果为

代码二

其实我们可以将上面的代码进行简化处理,我们可以在循环内只处理尾插,第一个结点放在外面处理

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/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* tail=NULL;//处理头节点if(list1->val < list2->val){newHead=tail=list1;list1=list1->next;}else{newHead=tail=list2;list2=list2->next;}//只要两个都不是空链表那么就可以继续执行下去while(list1 && list2){//1的值小于2的值时if(list1->valval){//尾插tail->next=list1;list1=list1->next;tail=tail->next;}//1的值大于等于2的值时else{//尾插tail->next=list2;tail=tail->next;list2=list2->next;}}if(list1==NULL){tail->next=list2;}else{tail->next=list1;}return newHead;
}

代码三

其实我们还可以使用一个哨兵位来解决第一个头节点的问题

代码如下

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/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* tail=NULL;newHead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//只要两个都不是空链表那么就可以继续执行下去while(list1 && list2){//1的值小于2的值时if(list1->valval){//尾插tail->next=list1;list1=list1->next;tail=tail->next;}//1的值大于等于2的值时else{//尾插tail->next=list2;tail=tail->next;list2=list2->next;}}if(list1==NULL){tail->next=list2;}else{tail->next=list1;}return newHead->next;
}

二、力扣第141题:环形链表

题目链接:141. 环形链表 - 力扣(Leetcode)

题目描述:

 

1.快慢指针法

其实这个题我们思考一下,如果它是一个环的话,那我们遍历一遍它就进入死循环了,如果不是环,就可以出来,但是这我们又无法知道它是否是死循环。有可能数据无限大,所以我们不能简单的凭借是否死循环来做这道题,那么就想,我们高中物理学过追及相遇问题,那么我们同样可以将思路带入到这里来。

我们是这样想的,使用两个指针,一个一次走一步,一个一次走两步。如果有环的话,那么快慢最终会相遇(下面有证明),如果无环,那么最终fast或者fast->next中必然有一个为空,因为有奇偶的讨论。所以顺着这个思路,这个代码很容易就写出来了

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* slow=head;struct ListNode* fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}

2.证明快慢指针是可行的

我们了解了上面的解法以后,我们也会产生一些疑惑,为什么快慢指针一定相遇,这里和物理中的追及相遇问题不一样的是,追及相遇问题是连续的,而这个问题是离散的。

我们的问题归纳一下就是:

slow一次走一步,fast一次走两步

1.slow和fast最后一定会相遇吗?有没有可能不会相遇?

2.slow一次走一步,fast一次走三步行不行?

slow一次走一步,fast一次走四步行不行

请证明:

我们先给出结论:

slow一次走一步,fast一次走两步一定可以相遇

我们可以这样思考

假设当slow刚进环的时候,fast和slow距离为N

那么fast和slow每一次他们的距离就-1,距离为N-1N-2 N-3...........0

最终一定会变为0。也就是相遇了。

所以一定可以相遇

那么slow一次一步,fast一次三步可不可以呢?

我们同样假设slow刚进环的时候相距为N

那么它们最终的距离就为N-2 N-4 N-6..........

我们可以看出来他们最终是要分情况讨论的,他们距离最近时候要么为0 要么为-1

0代表相遇,但是-1呢?-1其实代表着fast反超了slow一步

这时候我们假设环的总长度为C

那么我们此时fast和slow就相距为C-1的长度,而走一次他们的距离就减2

那么我们也可以看出来,当C为偶数的时候,永远不可能相遇

当C为奇数的时候才会相遇

所以fast一次走三步的时候还取决于N和C的长度。不一定会相遇

同样的,当一次走四步的时候也是同理的,不一定相遇

三、力扣第142题:环形链表Ⅱ

题目链接:142. 环形链表 II - 力扣(Leetcode)

题目描述:

 

1.解题思路

对于这道题,难点就在于如何求出这个入口,我们先给出结论

一个指针从相遇点走,一个指针从开头走,最终这两个指针将会在入口相遇

对于这个题目我们得先画图思考一下,如下图所示,假设这就是我们的链表

 设环为C长度,他们相遇点距离入口为X长度,他们的起始点距离入口为L长度

 已经fast的路程为L+X+N*C,slow的路程为X+L

slow的路程很简单,因为slow进入环以后,fast一定会在一圈之内追上slow,所以为L+X

这里大家比较疑惑的就是fast的路程,其实fast的路程是这样得到的,首先fast得先走一个L,这个毋庸置疑,然后当slow进环的时候,fast刚好走了一段距离,现在是fast正在追slow,这个时候slow走了x的时候,fast也刚好追上slow。而fast这时候其实就相当于走了N*C+X路程了,因为有可能直线特别大,圈特别小,fast在圈内走了好多圈了,slow还没有进来。所以走了N*C圈

 而又由于fast的速度是slow的两倍,时间相同,那么路程肯定也是两倍

所以得出

N*C+X+L=2*(X+L)

然后得出

N*C-X=L

而这个公式的含义就是

一个指针从相遇点走,一个指针从开头走,最终这两个指针将会在入口相遇

2.代码

 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast=head;struct ListNode* slow=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){struct ListNode* meet=slow;while(meet!=head){meet=meet->next;head=head->next;}return meet;}}return NULL;
}


总结

本小节讲解了三个经典的力扣题21.合并两个有序链表、141.环形链表、142.环形链表Ⅱ,希望大家都学会

如果对你有帮助,不要忘记点赞加收藏哦!!!

想获得更多有优质的内容,那么一定要关注我哦!!!

相关内容

热门资讯

安卓系统通知管理,全面解析与优... 你有没有发现,手机里的通知就像是一群调皮的小精灵,时不时地跳出来和你互动?没错,说的就是安卓系统的通...
安卓系统手机哪买,揭秘哪里购买... 你有没有想过,拥有一部安卓系统手机是多么酷的事情呢?想象你可以自由安装各种应用,不受限制地探索各种功...
安卓系统 ipv4,基于安卓系... 你知道吗?在智能手机的世界里,有一个系统可是无人不知、无人不晓,那就是安卓系统。而在这个庞大的安卓家...
目前安卓是什么系统,探索安卓系... 亲爱的读者,你是否曾好奇过,如今安卓系统究竟是什么模样?在这个科技飞速发展的时代,操作系统如同人体的...
安卓6.0系统比5.0,从5.... 你有没有发现,自从手机更新了安卓6.0系统,感觉整个人都清爽了不少呢?没错,今天咱们就来聊聊这个话题...
安卓2.36系统升级,功能革新... 你知道吗?最近安卓系统又来了一次大变身,那就是安卓2.36系统升级!这可不是一个小打小闹的更新,而是...
安卓系统源码怎么打开,并可能需... 你有没有想过,安卓系统的源码就像是一扇神秘的门,隐藏着无数的技术秘密?想要打开这扇门,你得掌握一些小...
安卓8.0系统体验视频,智能革... 你有没有听说安卓8.0系统最近可是火得一塌糊涂啊!作为一个紧跟科技潮流的数码达人,我当然要来给你好好...
宣传系统漫画app安卓,探索安... 亲爱的读者们,你是否曾在某个午后,百无聊赖地打开手机,想要寻找一些轻松愉悦的读物?今天,我要给你介绍...
鸿蒙替换安卓系统吗,开启智能生... 你知道吗?最近科技圈里可是炸开了锅,因为华为的新操作系统鸿蒙系统,据说要大举进军手机市场,替换掉安卓...
手机安卓系统深度清理,解锁手机... 手机里的东西是不是越来越多,感觉就像一个装满了杂物的储物柜?别急,今天就来教你一招——手机安卓系统深...
安卓上的windows系统,融... 你有没有想过,在安卓手机上也能体验到Windows系统的魅力呢?没错,这就是今天我要跟你分享的神奇故...
安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...
一加系统安卓降级,轻松还原经典... 你有没有想过,你的手机系统升级后,突然发现某些功能变得不那么顺心了?别急,今天就来聊聊一加系统安卓降...
日本最好的安卓系统,体验非凡 亲爱的读者们,你是否曾想过,在遥远的东方,有一个国家,他们的智能手机系统独具特色,让人眼前一亮?没错...
荣耀安卓11 系统证书,保障安... 你知道吗?最近手机圈里可是炸开了锅,荣耀安卓11系统证书成了大家热议的话题。这不,我就迫不及待地来和...
安卓手机开机升级系统,体验流畅... 你有没有发现,每次你的安卓手机开机,总会有那么一刹那,屏幕上跳出一个升级系统的提示?是不是觉得这就像...
真正的安卓系统手机,安卓系统手... 你有没有想过,为什么有些人对安卓系统手机情有独钟?是不是觉得市面上的安卓手机千篇一律,缺乏个性?别急...
安卓怎么用定位系统,轻松实现精... 你有没有想过,手机里的定位系统竟然这么神奇?它不仅能帮你找到回家的路,还能在茫茫人海中找到你的好友。...
安卓的哪个系统流畅,探索新一代... 你有没有想过,为什么你的安卓手机有时候像蜗牛一样慢吞吞的,而别人的手机却像风一样快?今天,就让我带你...