力扣——环形链表问题
判断链表是否有环以及入环的第一个节点
- 前言
- 判断链表是否有环
- 找到入环的第一个节点
前言
大家好，前段时间，熊二学习了关于环形链表相关的问题，以下是我的见解，希望能够帮助你们呀！
判断链表是否有环
给定一个链表，判断链表中是否有环。OJ链接
方法:快慢指针
思路:
如果没有环，快指针永远比慢指针快，，在这个追击问题中，慢指针永远追不上快指针，那么快慢指针永远都不会相遇，说明它们在一条直线上跑 ，故没有环。
如果有环，假设快指针是慢指针速度的两倍，那么快指针一定比慢指针先进入环，等慢指针开始进入环，这个追及问题就开始了，在同一个环中，快指针和慢指针速度不一至，快指针一定会追上慢指针的，当快指针=慢指针时，表明一定有环。
代码如下：
bool hasCycle(struct ListNode *head) {
struct ListNode *fast = head,*slow = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next;
if(slow == fast)
return true;
}
return false;
}
拓展问题：
1.为什么会相遇，有没有可能错过，永远追不上，请证明。
假设slow进环时，fast跟slow的距离是N,fast追击slow的过程距离变化如下:
N-1
N-2
…
3
2
1
0
每追击一次，fast与slow的距离是-减1,最后一定会追上
2.slow一次走1步，fast走3步，4步，5步，n步，一定能追上吗?请证明。
假设slow进环时，fast跟slow的距离是N,fast追击slow的过程距离变化如下:
若N为偶数 若N为奇数
N-2 N-2N-4 N-4
… …
4 3
2 1
0 1
追上了 错过了，进入新一轮的追击
新一轮，距离变成了C-1
C-1为偶数，下一轮就追上了
C-1为奇数，下一轮会不会追上呢？
关于C-1为奇数，下一轮会不会追上呢？我们暂且把问题变换成，如果同时存在N是奇数且C是偶数，fast会不会追上slow？
假设slow进环时，fast跟slow的距离是N
slow走的距离:L
fast走的距离:L+xC+C-N;
slow进环时，假设fast已经在环里面转了x圈
fast走的距离是slow的3倍
3L =L+ xC +C-N;
化简:
2L= (x+1)*C+C-N;
偶数 =(x+1)*偶数-奇数
如果同时存在N是奇数且C是偶数，
偶数 =(x+1)*偶数-奇数 ,不存在 ,所以，永远追不上不成立
总结：一定能够追上
找到入环的第一个节点
给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL。OJ链接
运动过程:
首先，我们指定快指针fast，慢指针slow，快指针以慢指针两倍的速度走(两指针同时走)。
当快指针进环时，慢指针还在追赶(红色)
当慢指针进环时，快指针已经在环里面(蓝色)，这时，不久后，快指针就会追上慢指针(在这个环中)
当快指针追上慢指针时(紫色)，我们从中寻找等式。设AB=L,BC=N，环的总长度为C,寻找关系
slow的路程:L+C-N
fast的路程:L+XC+C-N
fast是slow路程的两倍:2(L+C-N)=L+X*C+C-N;
继而得出:L=(X-1)*C+N;
因为C是圆环的长度，所以fast不管是多走X-1圈，还是多走了1圈，都没有区别，最后得出:L=N这个关键条件
代码如下：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
struct ListNode* meet = slow;
while(meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
