给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *fast =head;
struct ListNode *slow = head;
while(fast&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
//相遇
if(fast==slow)
{
return true;
}
}
return false;
}判断链表是否有环可以通过下面三步
第一步：当fast入环的时候，slow还没有入环
第二步：slow进环以后fast要追及slow
第三步： fast追上slow，就说明带环
第一个问题：为什么一定会相遇，有没有可能错过，永远追不上？
假设slow进环的时候，fast跟slow的距离是N
fast追击slow的过程中的距离变化如下：
切记：这里是fast走两步，slow走一步
N---->N-1---->N-2...2---->1----0==>每追及一次，距离就缩小1，距离为0就是追上了
第二个问题：slow 一次走一步，fast走3步，4步，5步或者n步的时候还能相遇？
这里以fast走三步证明
N 偶数 奇数
N N
N-2 N-2
N-4 N-4 ===> 每追击一次，距离就缩小2
.... ....
4 3
2 2
0 -1
|| ||
追上 第一轮错过，进行新的一轮追击，距离变成了C-1
距离为-1，错过了，进入新一轮，记环形长度为C，则距离变成了C-N
总结一下：
1，N是偶数，第一轮就能追上
2，N是奇数，第一轮追击就会错过，距离会变成C-1
a，如果C-1是偶数，下一轮就能追上
b，如果C-1是奇数，那么永远都追不上
是否同时存在N是奇数且C是偶数，那么就永远追不上？
假设slow进环的时候，fast和slow的距离为N
slow走的距离是：L
fast走的距离是L+x*C+C-N---》C-N为多走的
slow进环时，假设fast已经在环里转了x圈
fast 走的距离是slow的三倍
3*L= L+x*C+C-N
2*L=（x+1）*C-N
偶数=（x+1）*偶数-奇数
此时发现左右两边不能相等
所以N是奇数且C是偶数的情况不能同时存在，永远追不上的条件不成立
结论：
一定能追上
N是偶数第一轮就追上了
N是奇数第一轮追上上，C-1是偶数第二轮就能追上
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast =head,*slow = head;
while(fast && fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
{
struct ListNode*meet = slow;
while(head!=slow)
{
head=head->next;
slow=slow->next;
}
return slow;
}
}
return NULL;
}
L的长度其实是等于黑色这个长度
相遇时
slow走的路程：L+N
fast走的路程：L+x*C+N
fast走的路程是slow的2倍
2*（L+N）=L+x*C+N
L+N=x*C
L=x*C-N（x>=1整数）
也可以这样写L=（x-1）+C-N
标签：head,slow,struct,环形,fast,next,链表,证明 From： https://blog.csdn.net/weixin_49323800/article/details/140645097