📇文章目录
- 📜 LeetCode141. 环形链表
- 🔶题目描述
- 🔷思路分析
- ✔️代码实现
- 📜 LeetCode142.环形链表Ⅱ
- 🔶题目描述
- 🔷思路①
- ✔️代码实现
- 🔷思路②
- 📒总结
📜 LeetCode141. 环形链表
🔶题目描述
题目戳➡️LeetCode141.环形链表
给你一个链表的头节点
head，判断链表中是否有环.
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。
为了表示给定链 表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false
🔷思路分析
错误思路：
- 可能刚上来我们会这样想，遍历整个链表，如果找不到空说明就有环
但是有没有考虑过，如果链表有环，那么永远找不到空！ 不就死循环了吗
你的程序就崩溃了 所以这种思路是错误的！那么正确的思路是要怎么做呢？
➡️ 快慢指针定义一个
fast指针 和一个slow指针，
fast一次走两步，slow一次走一步
那么 ，如果fast走到尾 那么slow刚好走了链表的一半
如果fast走到了空 说明链表没有环- 如果
fast走到尾部 还没有停止 说明链表有环
fast进入环之后 就变成了追及问题（龟兔赛跑）
–那么我们就有思路了：如果快指针可以追得上满指针 说明有环！
–反之无环！但这时候又会有一个问题：链表的节点数是奇数还是偶数呢？
让我们画图分析：
➡️
- 奇数情况：
- 偶数情况
总结： 只要fast或fast->next有一个可以走到空 说明链表无环
否则一定有环，那么当fast追上slow的时候 返回真即可！
✔️代码实现
bool hasCycle(struct ListNode *head) { struct ListNode* fast=head,*slow=head;//定义一个快指针和慢指针//快指针一次走一步 慢指针一次走两步// 如果快指针走到空了 还没有找到交点 说明！没有环while(fast&&fast->next){fast=fast->next->next;slow=slow->next;//如果fast追上slow if(fast==slow){return true;}}return false; }📜 LeetCode142.环形链表Ⅱ
🔶题目描述
题目戳➡️LeetCode142.环形链表Ⅱ
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是 -1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表🔷思路①
上一个题我们可以挺容易的消除如何判断是不是有环，因为我们只需要判断有没有即可，不需要找出具体的在哪。但是这个题要求我们找出他的入环节点 这要怎么找呢？
其实这个题用到了一点数学知识，请听我分析：
首先还是利用快慢指针，定义一个快指针fast和一个慢指针slow，快指针一次走两步，慢指针一次走一步，然后如果有环，那么标记fast和slow的相遇节点为meet然后这个时候meet和head同时开始
向后走，等到他俩相遇的时候，这时候的节点就是入环的第一个节点！
画图分析：
- 所以 由上面的公式化简一下就得到：
L=(N-1)*C+(C-K)
从meet点开始转动N-1圈 再走C-K步 就等于 L的长度
如果N=1的时候 那么L=C-K
所以如果一个点在meet开始走，一个点在head开始走，那么 当二者相遇的时候，一定是在入环点！✔️代码实现
代码就很简单了：
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* meet=fast;while(meet!=head){meet=meet->next;head=head->next;}//相交的地方也就是 入环的节点！return meet;}}return NULL; }🔷思路②
还有一种思路就是
如果我们在fast和slow相遇的点meet处切开会发生什么呢？
如图：
是不是有点熟悉 ？没错！链表相交！那么解题思路就是：
首先找到meet节点，然后meet的下一个节点（nehead) 作为一个新的链表的头部，meet作为尾节点 ，所以这就变成了两个链表相交
所以我们遍历两个单链表找出各自的长度，让长的链表先走，走到二者长度相等的时候，一次比较两个链表的每一个节点，如果有相等n那么直接返回即可，如果没有相等的节点，那么返回空📒总结
🌟🌟🌟
环形链表问题在面试中是经常爱考的，你有没有发现环形链表的题目代码都没有很难，一般是思路难以想到，所以人家考你的是思路，并不真的会纠你代码写的怎么样！
对于环形链表①，如果面试官这样问你：
- 快指针必须一次走2步吗？可以一次走3步，走4步可以吗？你会怎么回答？
- 怎么证明快指针一次走2步一定可以追上？
这里我们简单证明一下：➡️快指针一次走2步那么一定可以追得上
首先需要知道，fast什么时候开始追击slow
因为fast首先进入环，在slow进环之前，二者的运动路径并不一样！只有当slow也开始进环，才开始所谓的追及问题
假设slow进环以后，fast与slow的距离是N
那么fast开始追击slow，二者相对速度为1 ，在追击过程中，它们之间的距离每一次都缩小1
所以距离的变化为：N–> N-1 -->N-2–>···->3–>2–>1–>0
所以一定可以追得上！
➡️可以一次走3步吗
假设slow进环的时候以后，fast与slow的距离为N，环的大小是C
这时候，如果fast开始追击slow，fast一次走3步，slow一次走1步，
他们之间的距离一次缩小2步
- 如果N为偶数
那么N的变化为：N->N-2->N-4->···->4->2->0 显然可以相遇- 如果N为奇数
那么N的变化为： N->N-2->N-4->···->3->1->-1!
那么slow和fast之间的距离为-1（擦肩而过！) , 他们之间的距离变成了C-1这时候如果C-1为偶数那么可以相遇，如果C-1为奇数那么永远不会相遇！
画图看一下：
🌟🌟🌟
