/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        //双指针算法，一个指针一次走一步，一个一次走两步，当相遇是，慢指针回到head,快指针
        //在当前位置，然后两个同时走一步，当相遇时即为入口，证明见Y总题解,注意，如果没有环
        //快指针会停留在null上
        if(!head) return nullptr;
        auto p = head,q = head;
        while(p && q){
            p = p->next;
            q = q->next;
            if(q->next) q = q->next;
            else return nullptr;

            if(p == q){
                p = head;
                while(p != q) p = p->next,q = q->next; 
                return p;
            }
        }
        return nullptr;
    }
};