LeetCode 142.环形链表2

思路：

1. 用两个指针 slow和fast, 都从起点开始走，slow 每次走一步，fast每次走两步。

2. 如果过程中 fast走到null，则说明不存在环。否则当slow 和fast 相遇后，让 slow返回起点，fast待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。

分析：

1. 两个指针fast和slow同时从a出发；
2. 当slow走到b时，fast走到c’，slow走过的距离为x，fast走过的距离为2x；
3. 此时slow再往前走y距离，则fast会从c’往前走2y距离，fast和slow在c处相遇相遇；
4. 将slow移动到a处，fast不动，仍在c处，此时同时移动slow和fast，每次都移动一位；
5. fast和slow会在b处相遇，因为c到b的距离为x，等于a到b的距离

class Solution {


public:
    ListNode *detectCycle(ListNode *head) {
        auto fast = head, slow = head;
        while (slow && fast){
            fast = fast->next;
            slow = slow->next;
            // 快指针走两步
            if (fast) fast = fast->next;
            else break;

            // 当两个指针相遇
            if (fast == slow){
                // slow放回开头，两个指针再每次都往前走一步
                slow = head;
                while (slow != fast){
                    fast = fast->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};