您现在的位置是:首页 >技术交流 >力扣---LeetCode141/142. 环形链表 (I)和(II) (代码详解+流程图+数学逻辑拓展)网站首页技术交流
力扣---LeetCode141/142. 环形链表 (I)和(II) (代码详解+流程图+数学逻辑拓展)
简介力扣---LeetCode141/142. 环形链表 (I)和(II) (代码详解+流程图+数学逻辑拓展)
文章目录
前言
“山前山后都有风景有风无风都很自由”
本章的内容是力扣每日随机一题的部分方法的代码解析以及流程图
提示:以下是本篇文章正文内容,下面案例可供参考
141. 环形链表 I
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
1.1 链接:
141. 环形链表 I link
1.2 思路:
定义一个快指针(一次走两步)一个慢指针(一次走一步)转换成龟兔赛跑的问题,最终都会进环当快指针追上慢指针就证明有环,若没环就不会出现快指针追上慢指针的情况走到快指针为NULL就结束了
1.3 代码:快慢指针
bool hasCycle(struct ListNode *head)
{
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
{
return true;
}
}
return false;
}
1.4 流程图:
142. 环形链表 II
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改链表。
2.1 链接:
142. 环形链表 II link
2.2 思路:
一个指针从相遇点走,一个指针从链表头开始走,他们会在入口点相遇.
特殊推论:
通用推论:
2.3 代码:
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *fast=head;
struct ListNode *slow=head;
struct ListNode *meet=NULL;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
{
meet=slow;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return head;
}
}
return NULL;
}
2.4 流程图:
拓展问题及证明(面试常问):
3.1 slow和fast一定会相遇吗?(slow一步,fast两步)
3.1.1答案:(每次缩小1)一定会相遇
3.1.2证明:
3.2 slow走1步,fast走n(3/4/5.…)步可以吗?(n > 2)
3.2.1答案:不一定相遇
3.2.2证明:
总结
Ending,今天的力扣每日一题内容就到此结束啦,如果后续想了解更多,就请关注我吧,一键三连,还有许多种方法没有写出希望各位佬补充哦~
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。