视频讲解

①Y+Z是环的长度，两指针在环中相遇

②经历同样的时间，由于 快指针速度 = 2*慢指针，有

③化简得

④由于n>=1

等式④表示一个指针从head开始，一个指针从相遇处开始，在其经历(n-1)圈后最终在入口X处相遇，即为题目所求

/**
 * 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) {
        auto fast = head, slow = head;
        while( fast )
        {
                slow = slow->next;
                fast = fast->next;
                if( fast ) fast = fast->next;  // 为空说明没有环，走到底了
                else break;
                if( fast == slow )  // 相遇
                {
                        auto i = head;
                        auto j = fast;  // 从相遇的地方开始
                        while( i!=j )
                        {
                                i = i->next;
                                j = j->next;
                        }
                        return i;
                }
        }
        return NULL;
    }
};