题解 | #链表中环的入口节点#(快慢指针且相遇到入口长度 +k圈=开始到入口长度 )

• 设置两个指针一个快指针每次走两步（fast->next->next），一个慢指针一次走一步(low->next)。
• 如果链表中没有环它们最后肯定不相遇，反之它们一定会在环中相遇。
• 如上图链表中有环，从x点出发，环的入口为点y，它们最后会在z点相遇。
  • 设x到y长度为a，y到z的长度为b，z到y的长度为c，快指针在环中绕了k圈，在k+1圈与慢指针相遇。
  • 慢指针走了a + b的长度，快指针走了 a + k(b + c) + b ，
    因为快指针每次走的是慢指针的两倍。
    则 2*（a + b）= a + k(b + c) + b 。
    化简 得 a = (k-1)(b + c) + c。
  • 即x到y的长度 = k-1圈环的长度 + z到y的长度。即当一个指针从头x开始走，另一个指针从相遇点z开始走,当它们相遇时候一定是在环的入口y。

/**

2*(a + b) = a + k*(b+c) + b
a = (k-1)*(b +c) +c
当指针从头开始，走到环的入口刚好等于另一个指针从相遇位置走(k-1)圈 到达 环入口

 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast,*low;
        low = fast = head;
        bool noRing = true; // 是否存在环
        while(fast && fast->next){ // NULL->next 会报错
            low = low->next;
            fast = fast->next->next;
            if(low == fast) {
                noRing = false; // 有环
                break;
            }
        }
        if(noRing) return NULL; // 没有环 返回
        fast = head;
        while( fast != low){
            fast = fast->next;
            low = low->next;
        }
        return fast;
    }
};