《代环问题》

代环问题

什么是代环
- 代环的结构
怎么判断代环还是不代环呢？
举一反三
- 1：为什么一定会相遇,有没有可能会错过永远追不上? 请证明
- 2:slow一次走一步，那么fast走3、4、5、6......n步可不可以?
- N是奇数C是偶数时，那就永远追不上这个条件存在吗？
- 找代环入口点
总结

什么是代环

在这里插入图片描述

代环的结构

尾结点的next指针有可能指向任意的位置

怎么判断代环还是不代环呢？

1：要运用到快慢指针
慢指针走一步，快指针走俩步
2：当slow指针走到环中，那么就与fast指针形成追击问题（fast走俩步，slow走一步）期间fast在一步一步的追击slow，直到他们相遇
在这里插入图片描述

//函数实现
bool shfes(struct ListNode* head)
{
struct ListNode* slow=head,*fast=headl
while(fast&&fast->next)
{
slow=slow->next;//慢指针走一步
fast=fast->next->next;//快指针走俩步
if(slow==fast)
return true;
}
return flase;
}

举一反三

代环链表有很多的考点
比如：

1：为什么一定会相遇,有没有可能会错过永远追不上? 请证明

在这里插入图片描述
首先: 我们先设slow进环时与fast的差距是N.
那么我们就可以得知fast与slow的追击过程
N
经过一次后
N-1
经过俩次后
N-2
、、、、、、以此类推
经过N次后
这时他们刚好相遇

2:slow一次走一步，那么fast走3、4、5、6…n步可不可以?

fast走3步，slow走1步

当slow进环时那么与fast也形成了追击问题
fast与slow追击过程
我们设他们的差距是N
(N是偶数) (N是奇数)
N ----------------- N
N-2 -------------- N-2
N-4 -------------- N-4
… ----------------- …
4 ------------------3
2 ------------------1
0 ---------------- -1(这里表示fast指针超过了slow，错过了slow，要进入新一轮的追击)

那么我们设这个环的周长为C

错过了slow,进行新一轮的危机
距离变成C-1

再重复上述过程
1：现在的C-1变成了fast与slow指针的差距N
2：如果C-1是偶数，那么fast下一轮就追上了
3：如果C-1是奇数，那么fast就永远追不上了(死循环)

复盘：
如果N是偶数，fast第一轮就追上了。
如果N是奇数，fast第一轮就错过了，
1：如果C-1是偶数，那么下一轮就追上了。
2：如果C-1是奇数，那么就永远追不上了。

N是奇数C是偶数时，那就永远追不上这个条件存在吗？

在这里插入图片描述

当slow进环时，fast已经在环中转了x圈了
fast走的距离：L+xC+C-N(转了x圈且多走C-N圈)
slow走的距离：L
fast指针一次走3步，而slow指针一次走1步
得知：
fast走的距离是slow的3倍
**L+xC+C-N=3L
(x+1)C-N=2L*
左边2L是偶数那么右边也得是偶数

如果按照条件：N是奇数C是偶数
*偶数=(x+1)偶数-奇数------------>偶数=偶数-奇数
通过带入可知：

这个条件：N是奇数C是偶数不成立！！！
总结
永远追不上的条件不成立！！！