【LeetCode】环形链表+结论证明

题目链接：环形链表

题目：给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例1:

示例2：

• 解体思路  快慢指针

分别定义 fast 和 slow 指针,两个指针同时从头节点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。fast或者fast->next走到空指针，则该链表无环.

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* show = head;
    while(fast && fast->next)
    {
        fast = fast->next->next; //一次移动两步
        show = show->next;       //一次移动一步
       // 快慢指针相遇，说明有环
        if(fast == show)
            return true;
    }
    return false;
}

很多人会有疑问：

1、slow和fast一定会相遇吗?

2、slow走1步，fast走3步可以吗?

• 问题一证明：

一定会，fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N，slow进环以后，fast开始追击slow，slow每走1步，fast每走2步，他们之间距离缩小1，追击过程中，他们之间的距离变化：

N

N-1

N-2

......

2

1

0

到0时候fast就会追上了，所以fast指针每次移动两个节点，slow指针每次移动一个节点，只要有环是不会错过的，肯定是会相遇的。

• 问题二证明：

不一定，fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N，slow进环以后，fast开始追击slow，slow每走1步，fast每走3步，他们之间距离缩小2。他们之间的距离变化：（分奇偶数分析）

N -> 偶数  奇数

       N        N

       N-2     N-2

       N-4     N-4

       N-6     N-6

       ....       ....

       4         3

       2         1

       0        -1

   偶数：每次走fast每次走三步，slow每次走一步，要是有环也是会相遇的。

   奇数：会进入进入新一轮的追击，slow和fast的距离变成C-1 (假设C是环的长度)，如果C-1是偶数那么下一轮可以追上，如果C-1是奇数那么永远追不上。