寻找环形链表入口点的第一步,要先判断该链表是否为环形链表,环形链表的尾指针指向的位置是不确定的,它可以在任何位置成环。
如下面这些图所示:
那么如何判断是否有环呢?我们可以采用双指针法,思路如下:
具体地,我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。初始时,快、慢指针在位置 head。这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。
代码如下:
bool hasCycle(struct ListNode *head)
{
struct ListNode *slow=head; //慢指针
struct ListNode *fast=head; //快指针
//慢指针一次走一步,快指针一次走两步
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
对于以上代码我们难免会提出以下两个问题;
答:
不会追不上。假设slow进环的时候,fast与slow的距离是N,紧接着追击的过程中(fast追slow)fast向前走两步,slow走一步,他们每次一走,它们之间的距离就会缩小1,由一开始相距N,到后面相距0。
![在这里插入图片描述](https://img-blog.csdnimg.cn/2021041323160443.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzgxMjYwMw==,size_16,color_FFFFFF,t_70
进环后fast与slow的距离 |
---|
N |
N-1 |
N-2 |
… |
… |
2 |
1 |
0 |
从表中我们会发现它们之间的距离就会缩小1由一开始相距N,到后面相距为0。
不管进环时,它们相距的距离是偶数还是奇数。最终我们发现一定fast一定会追上slow。
例如下面这个例子:
假设环里面只有8个节点,此时如slow与fast的位置如左下图所示:
最终fast与slow会在相遇点相遇
此时我们就可以发现要发生相遇与fast走的步数和环中的节点数有关。
我们设fast走X步,环中结点数为Y
经过上图我们分析我们可以写出如下代码:
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* slow = head; //慢指针
struct ListNode* fast = head; //快指针
//慢指针一次走一步,快指针一次走两步
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
//相遇结点
struct ListNode*meet=fast;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return meet;
}
}
return NULL;
}
如果你很在意你的终端的外观的话,一个跨 shell 的提示符可以让你轻松地定制和配...
Asp 解析 XML并分页显示,示例源码如下: 复制代码 代码如下: !DOCTYPE html PUB...
我之前写过一个简易版的自动+手动轮播图: 简易轮播图 但是这个轮播图在切换的时...
例如: 我们在百度中搜索 尊托云数,则网址后面的参数就是 http://www.baidu.com/...
发现每个编辑实例都可以加载不同的css样式表,而且其样式不继承 页面的css。 于...
主要目的 a. 掌握获取 GridPanel 当前行的各个字段值的方法 b. 掌握如何将前台数...
关于我的SWFObject V1.5的使用过程,以 上篇 中的介绍暂时告一段落了,下面我将...
Mysql数据库五——mysql事务及引擎 一、事务 1、事务的概念 2、事务的ACID特点 ...
接着昨天的,如果forEach中的items类型是map或者Collection类型的,怎样使用增强...
本文实例为大家分享了js实现电灯开关效果的具体代码,供大家参考,具体内容如下 ...