环形链表的
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
一、环形链表是什么?
简单来说:就是带环的链表(具有环形结构的链表)
如图所示 的俩个链表都是环形链表
二、环形链表的相关问题
目录
1.我们该怎么判断环形链表?
方法:快慢指针(fast and slow)
慢指针:一次走一步 快指针:一次走俩步 (至于为什么一般的快指针一般走俩步,后面会做出解释)
大概思路变化图为:(忽略画工)
接着slow往前走一步走到节点1处,fast往前走俩步走到节点2处
fast再移动俩步,就会进入环中,从2走到0再走到1,slow则是继续往前挪动到第二个2位置处,接下来很容易就会看出slow和fast会在0节点处汇合
即为下图
具体代码:
-
//快慢指针
-
bool hasCycle(struct ListNode *head) {
-
struct ListNode*slow=head,*fast=head;
-
while(fast&&fast->next)//处理奇偶个节点
-
{
-
fast=fast->next->next;
-
slow=slow->next;
-
if(slow==fast)
-
{
-
return true;
-
}
-
}
-
return false;
-
}
其中为什么循环的出口为什么是fast和fast->next,是因为如果链表没有环状时,如果链表含有奇数个节点,那么循环会从fast->next走出,此外链表中有偶数个节点就会从fast走出(如果此时将fast->next放在&&前面会报错,因为fast=NULL,而NULL->NULL,是不被系统允许的。)
到这,我相信你们也会和我有一样的疑惑,就是为什么快指针是一次走俩步,而不能走n步呢?(n>2),且为什么环状链表,快慢指针就一定会相遇呢?
下面给出证明:
而升序n=4,n=5....的情况都是类似推导的
2.环形链表的环形入口点该怎么确定
由上文,我们可得知,快慢指针是一定会在有环状结构的链表中的环中相遇。而我们的思路就是从此推出来的结论:从头节点出发的指针一定会和从快慢指针相遇点出发的指针汇合于环入口点。
最后再赋上我的代码(可优化)
-
-
//思路1 :推论:一个从头节点出发的指针和一个从快慢指针的相遇节点出发的指针最后会在入口节点相见
-
struct ListNode *detectCycle(struct ListNode *head) {
-
if(head==NULL||head->next==NULL)
-
return NULL;
-
struct ListNode*slow=head,*fast=head;
-
while(fast&&fast->next)
-
{
-
fast=fast->next->next;
-
slow=slow->next;
-
if(slow==fast)
-
{
-
break;
-
}
-
}
-
if(fast!=slow)
-
return NULL;
-
struct ListNode* meetNode=fast;//or slow
-
struct ListNode* find=head;
-
while(meetNode!=find)
-
{
-
meetNode=meetNode->next;
-
find=find->next;
-
}
-
return meetNode;
-
}
总结
结论:
- 快指针一次走俩步一定会和慢指针在环中相遇,一次走N步时需要进行讨论
- 从头节点出发的指针一定会和从快慢指针相遇点出发的指针汇合于环入口点。
以下是俩道题的链接,帮助我们巩固知识
https://leetcode-cn.com/problems/linked-list-cycle/description/
https://leetcode-cn.com/problems/linked-list-cycle-ii/description/
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfigkai
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24