环形链表 II

实质上就是链表中环的入口节点
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

1.初始化：定义两个指针 fast 和 slow，它们都指向链表的头节点 pHead。

2.快慢指针移动：fast 每次向前移动两步，slow 每次向前移动一步。如果链表中存在环，fast 和 slow 指针最终会在环内相遇。

3.检测环的存在：在循环中，如果 fast 或者 fast->next 为 NULL，则链表中不存在环，返回 nullptr。

这里涉及一个数学关系。
设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast相遇。此时，fast指针已经走完了环的 n 圈，因此它走过的总距离为
a+n(b+c)+b=a+(n+1)b+nc
任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。
a+(n+1)b+nc=2(a+b)
所以
a=c+(n−1)(b+c)
即从相遇点到入环点的距离加上 n−1圈的环长，恰好等于从链表头部到入环点的距离。

4.相遇点：如果 fast 和 slow 相遇（fast == slow），则链表中存在环，将 res 设置为 true 并跳出循环。

5.寻找环的入口：如果检测到环，重置一个指针 cur 指向 pHead，同时 fast 指向相遇点。然后，cur 和 fast 都每次向前移动一步，当它们再次相遇时，这个相遇点就是环的入口节点。

6.返回环的入口节点：返回 fast，它指向环的入口节点。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
    if(pHead==NULL || pHead->next==NULL) return nullptr;
    bool res=false;
    ListNode* fast=pHead;
    ListNode* slow=pHead;
    while(fast!=NULL && fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow) 
        {
            res=true;
            break;
        }
    }
    if(res==false) return nullptr;
    else
     {
        ListNode *cur=pHead;
        while(cur!=fast)
        {
            cur=cur->next;
            fast=fast->next;
        }
        return fast;
     }
    }
};