lc142.环形链表Ⅱ

采用双指针+模拟

双指针采用快慢指针，快指针每次走一步，慢指针每次走两步，最后两个指针如果相遇一定是在环里面，如果没有相遇就说明没有环，因此实现了判环。

如何找到环的入口，题解，通过模拟的方法找到关系式，然后实现。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) { //模拟+链表+双指针
        auto fast = head,slow = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast)                //说明有环
            {
                auto p = fast,q = head;
                while(p != q)
                {
                    p = p->next;
                    q = q->next;
                }
                return q;
            }
        }
        return nullptr;

        
    }
};