脚本宝典收集整理的这篇文章主要介绍了【LeetCode.链表.141+142】环形链表,附详细证明过程+多图分析,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
📝题目指路:141. 环形链表 - 力扣(LeetCode) (leetcode-cn.COM)
🎷首先题目已经给出了思路:
next
指针再次到达,则链表中存在环👞👞这就类似于追赶/追及
的问题,我们经常用到的是 快慢指针
👞👞
我们将上面的链表图转换为更为简单的直观图
fast
和slow
两个人赛跑🎯等到slow
开始进入环的时候,开始追及问题
🎯假设 环的长度为C
🎯此时fast
和slow
相差C - X
🎯而fast追slow的时候,每一步都会使得C-X
少1
🎯所以最终他们会相遇
🎯如果他们相遇
了,证明这是个环
slow遇不到fast,fast先遇到NULL
,证明这不是个环📖📖代码如下:
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;
}
📝题目指路:142. 环形链表 II - 力扣(LeetCode) (leetcode-cn.com)
先回到一开始,slow
进入环,fast
开始追击的时候
📌假设 环的长度为C
📌此时fast
和slow
相差C - X
(fast追slow)
📌设slow
和fast
走了t1
次
📌slow
的速度是1
个节点/次,fast
的速度是2
个节点/次,
📌二者相遇之前,是fast
追slow
,fast
和slow
相差X
📌列出式子2t1 - t1 = X
又因为 t1 = L
📌得出:t1 = X = L
相遇的时候
从这里开始计时,
✒️设slow
和fast
走了t
次
✒️slow
的速度是1
个节点/次,fast
的速度是2
个节点/次
✒️二者相遇之前,是fast
追slow
,fast
和slow
相差C - X
✒️列出式子2t - t = C - X
✒️得出:t = C - X
✒️slow走了C - X
💡从此时相遇且从此时开始我们定义一个 新指针指向链表起点
💡slow
再开始一步一步走,直到,cur
和slow
地址相同,找到环形的入口
📒📒代码如下:
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 *cur = head;
while(slow != cur)
{
cur = cur->next;
slow = slow->next;
}
return cur;
}
}
return NULL;
}
以上是脚本宝典为你收集整理的【LeetCode.链表.141+142】环形链表,附详细证明过程+多图分析全部内容,希望文章能够帮你解决【LeetCode.链表.141+142】环形链表,附详细证明过程+多图分析所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。