题目如下

思路与代码

1.双指针找到相遇点，慢指针走一步，快指针走两步，它们肯定会相遇的，因为相对速度是一步，不会错过，哎，快指针真的是个舔狗…

---

2.看图说话

a：链表头到环入口的长度
b：环入口到相遇点的长度
c：相遇点到环入口的长度

相遇时：
快指针路程=a+(b+c)*k+b,k>=1,其中b+c为环的长度，k为绕环的圈数
慢指针路程=a+b
快指针走的路程是慢指针的两倍，所以：
(a+b)*2=a+(b+c)*k+b

化简可以得到 a=(k-1)*(b+c)+c 链表头到环入口的距离=相遇点到环入口的距离+(k-1)圈环长度
所以，两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode*fast=pHead,*low=pHead;
        while(fast&&fast->next){
            fast=fast->next->next;
            low=low->next;
            if(fast==low)
                break;
        }
        if(!fast||!fast->next) return NULL;
        low=pHead;
        while(fast!=low){
            fast=fast->next;
            low=low->next;
        }
        return low;
    }
};