环形单链表问题

1. 链表有无环判断方法

思路：

利用快慢指针，如果快每次走两个，慢指针每次走一个，则最终必然会相遇。

证明：
先猜想：是否快会跟慢永不相遇，在环内可能跨过慢

存在环时，快先入环，慢后入环，假设慢入环时，两者相差N，快慢指针两者每走一次，相差1，所以两者的差距N会有消为0的时候。

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    // 要做fast->next遍历，但是只写while f->next必然会出错 因f会有不存在情况
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 带环链表快慢指针相追赶问题

假设慢指针是s，快指针是f

1. s走1，f走3，两者一定会相遇吗？

1. 设进入环后差为N，s、f每走一次，两者差距变为N-2，N-4，N-6，如果N是偶数，那么会有为0的情况，如果N是奇数，就不会相遇。因为差距会从1到-1、-3。。。

2. s走1，f走4，两者会相遇吗？

设进入环后差为N，s、f每走一次，两者差距变为N-3，N-5，N-7，所以也不一定相遇。N为3的倍数，可能会相遇。

3. s走1，f走n，两者会相遇吗？

由2我们已经能推出来了，如果两者入环后的差距N是两者速度差n-1的倍数，那么就会相遇。

4. s走m，f走n，两者会相遇吗？

仍然是：若 ** N % (m-n) == 0：则必定相遇 **，其它情况，可能相遇也可能不想与

3. 环节入口点判断、相遇节点判断

1. 求交点：假设快f指针是慢指针s的两倍。
2. 当相遇时，f、s走过的路程设为sf、ss。则有 sf = 2ss。
3. 假设入环前，长度为L，入环后，至相遇走了X，Ss = L+X+Mc Sf = L+X+Nc，M和N分布代表它们俩入环后走了几圈才相遇。而慢指针不可能走1圈，S刚入环后，两者差N，而两者的距离n小于C，因为两者差距不可能是环大小，n
4. Ss = L+X，Sf = L+X+Nc。再由于两者2倍的关系： 化简得到：
5. L+X = NC => L = NC-X => L = (n-1)C+C-X
6. 由最后一个公式可以理解到：两个指针以同样的速度，一个在环外起点，一个在环内相遇点（相遇点可用本文部分1中方法求得）开始走，最终会在C-X处相遇，C-X即环入口。
   最后，我再留一张，自己推算的稿纸：