1. 判断链表是否有环

1.1 题目

题目链接：链表带环问题

1.2 思路及题解

这道题要说思路很简单，还是应用了“快慢指针”的思想。
【结论】快指针fast一次走两步，慢指针slow一次走一步。若带环，fast会在环内追上slow；如果无环，永远不可能再相遇，且·fast会先为空。

这样我们可以很轻易的写出代码。这只是最基本的追及问题，同时也严谨的疑惑着，为什么快指针一次走两步慢指针一次走一步可以？快指针一次走3、4、n步行吗？这道题目重点在于如何推导出上述结论。

bool hasCycle(struct ListNode *head) {
    struct ListNode * slow = head;
    struct ListNode * fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return true;
    }
    return false;
}
 

1.3 证明

:black_heart: 1. 为什么slow和fast一定会在环中相遇？会不会错过，永远遇不上？
slow和fast，一定是fast先进环，此时slow走了进环前距离的一半。
随着slow进环，fast已经在环内走了一段（走了多少跟环的大小有关）。设slow进环时，fast和slow距离是$N$，则slow和fast每追一次，差距缩小一步，判断一下是否相遇，距离变化$N-1,N-2,N-3 ，....2,1,0$。一定会到0，则一定能相遇。

:black_heart: 2. 为什么slow走一步，fast走两步？能不能fast走3/4/5/n步？
结论：fast走$n(n>2)$步，不一定能遇上。

(1) 若fast一次走三步

(2) 若fast一次走4步

fast走$N$步，$N$再变大，以此类推，都是不行的。

2. 找入环点

2.1 题目

题目链接：找到环的入口点

2.2 思路及证明

slow走一步，fast走两步，一定会相遇，如何求环的入口点呢？
【结论】一个指针从相遇点开始走，另一个指针从链表头开始走，它们会在环的入口点相遇。
【证明】追上的过程中
慢指针走的距离：$L+x$ （慢指针不可能超过一圈，$N<C$）
快指针走过的距离：$L+n*c+x$
快指针走过的路程是慢指针的2倍：$2(L+x) = L+n*c+x$

2.3 题解

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* meetnode = NULL;
    //1.找到他们相遇的点
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
        {
            //相遇
            meetnode = fast;
            //寻找入环点--公式证明
            while(head != meetnode)
            {
                head = head->next;
                meetnode = meetnode->next;
            }
            return meetnode;
        }
    }
    return NULL;
}

持续更新中@边通书