目录
题目1
示例
解题思路
代码实现
补充
题目2
示例
解题思路
代码实现
题目1
该题链接：https://leetcode.cn/problems/linked-list-cycle/description/
示例
解题思路
要创建两个指针一个是快指针(fast)，另一个慢指针(slow)。快指针走两步慢指针走一步，让它们一起往后走，如果它们相等即存在环。
为什么它们相等即存在环呢？
我们先假设一个链表存在环。让fast和slow一起从起始位置走。fast肯定先进环。当slow走到环的入口处时，假设fast与slow的距离为N。fast走两步，slow走一步，这时N会变成N-1。只要它们一直走，N一定会等于零，这时候它们相遇，即存在环。
代码实现
这里着重讲一下循环结束条件。
- 如果没有环，因为fast走的快所以它会先遇到NULL。要另外加上fast->next这是为了防止对NULL进行解应用。
- 如果有环直接返回即可。
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return true;
}
return false;
}补充
为什么快指针要走两步走三步不行吗？四步呢？n步呢？这里我介绍fast走三步的情况。
假设环的总长度为C。根据上面我介绍的如果N为奇数第一轮它们不会相遇。第二轮它们的距离是C-1，如果C-1是奇数那它们就永远就遇不到了。
总结一下:
1、N是偶数，第一轮就追上了
2、N是奇数，第一轮追击会错过，距离变成C-1
a、如果C-1是偶数，下一轮就追上了
b、如果C-1是奇数 那么就永远追不上
同时存在N是奇数且C是偶数，那就永远追不上
让我们来证一下
假设现在slow现在在入环口。设slow走的距离为L ，fast走的距离为L+X*C+C-N(X是fast在环里转的圈数)。
因为3slow=fast。所以3L=L+X*C+C-N。化简得2L=(X+1)C-N。
分析：2L为偶数，将上面的不存在条件带入会发现该等式并不成立，所以走三步会遇到。
题目2
该题链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
示例
解题思路
先设个快慢指针如果存在环则它们一定会相遇，当它们相遇时设一个meet指针指向它们相遇位置，在设一个head指针指向链表头节点。让它们同时走每次走一步，当它们相等时即找到入环的节点。
解释：假设从头结点到入环节点距离为L，入环节点到fast和slow的相遇点距离为N。
fast走的距离L+X*C+N(X是圈数)，slow走的距离L+N。因为2slow=fast得
2(L+N)=L+X*C+N，化简得：L=(X-1)C+C-N。即L=C-N。
代码实现
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
ListNode* meet = slow;
while(meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
