当前位置:网站首页>环形链表问题(判环、求入口点)
环形链表问题(判环、求入口点)
2022-08-09 07:33:00 【-YIN】
判断链表中是否有环
废话不多说直接上题
题目链接:141. 环形链表
题目示例
如何判断链表中是否带环?
[思路]:快慢指针遍历链表,(快指针每次走两步,慢指针每次一步),如果链表中存在环那么快慢指针一定会相遇,否则快指针会先到达链尾。
就好比带环就是在操场绕圈跑步,不管什么时候开始、如果一直跑,跑的快的一定会追上跑的慢的人
【问题】那为什么快指针每次走两步,三步可以吗?四步…
• 为什么快指针走两步,慢指针走一步可以?
假设链表带环,两个指针都会先后进入环内,快指针先,慢指针后进。
- 可能当慢指针刚进环时,可能就和快指针相遇了(最理想情况)
- 最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步
因此:在慢指针走完一圈之前,快指针肯定是可以追上慢指针的,即相遇。不会存在套圈的情况
• 快指针一次走3步,走4步,…n步行吗?
答案是不行!
如果快指针每次走3步,慢指针走一步,假设进环时两指针位置如图所示:
可以发现上图中快指针每次都将慢指针跳过套圈,所以循环无法满足条件退出(4步情况同理);所以只有快指针每次走一步才满足所有情况
源代码:
第一个题,链表判环代码如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
/* 两个指针从链表其实位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾 */
bool hasCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
// 每移动一次检测是否在同一位置
if(fast == slow)
return true;
}
return false;
}
};
如果有环,如何找到这个环的入口
题目链接:142. 环形链表 II
此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。
先给出结论 方便做题使用
结论:
一个指针从起始位置开始,另一个从快慢指针相遇位置开始,每次都移动一个节点,最后相遇点就是环的入口。
推导过程
所以不管快指针走了n圈,反正都是相遇点为M,环入口点为E都是固定的,
所以从快指针到入口点距离和起点到入口距离一定相等
源代码:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
// 判断是否存在环,存在返回快慢指针相遇节点;不存在返回nullptr
ListNode* hasCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return fast;
}
return nullptr;
}
ListNode *detectCycle(ListNode *head) {
ListNode* cur = hasCycle(head);
if(cur == nullptr) return nullptr;
ListNode* cur1 = head;
while(cur1 != cur){
cur1 = cur1->next;
cur = cur->next;
}
// 相遇节点为环入口
return cur;
}
};
上述代码存在冗余,优化后如下
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
ListNode* cur = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
// 快慢指针相遇,此时从head 和 相遇点,同时查找直至相遇
if(fast == slow){
while(fast != cur){
fast = fast->next;
cur = cur->next;
}
// 相遇节点为环入口
return cur;
}
}
return nullptr;
}
边栏推荐
- 线程API
- Better Scroll Y上下滚动无法上拉滚动解决办法
- rsync:recv_generator: mkdir (in backup) failed:Permission denied (13) |failed to set times on '.'
- 【机器学习】降维代码练习
- C语言:汽水瓶详解
- PyTorch中 torch.nn与torch.nn.functional的区别
- 类和结构体
- 【转载】Deep Learning(深度学习)学习笔记整理
- imageio读取.exr报错 ValueError: Could not find a backend to open `xxx.exr‘ with iomode `r`
- 用tensorflow.keras模块化搭建神经网络模型
猜你喜欢
随机推荐
MUV LUV EXTRA 2019CCPC秦皇岛站J题 KMP
yolov5 detects the number of labels in the dataset
Data storage implementation of SDRAM and read and write operations on its data
JSONObject遍历的时候顺序不一致,导致数据对应出错
差分约束-图论
生成对抗网络GAN:Generative Adversarial Networks
failed (13: Permission denied) while connecting to upstream
eyb:Redis学习(2)
学习小笔记---机器学习
更改Jupyter Notebook默认打开目录
(五)、马尔科夫预测模型
MUV LUV EXTRA 2019CCPC Qinhuangdao Station J Question KMP
Lottie系列二:高级属性
【Template】Tree Chain Segmentation P3384
LeetCode:876. 链表的中间结点————简单
Invoker 2019CCPC Qinhuangdao Station I Question Simple DP
SAP ALV 数据导出被截断的bug
高德地图JS - 已知经纬度来获取街道、城市、详细地址等信息
Colors that Tkinter can choose from
jmeter concurrency and some limitations of the press