快慢指针-找链表环的入口点_快慢指针循环链表入口

分别定义快指针p、慢指针q，初始时两指针均指定链表首结点；快指针每次移动两个结点，慢指针每次移动一个结点；

1. 若链表有环则指针 p、q 一定会相遇（来源数学龟兔赛跑问题），否则快指针为空时返回nullptr；

2. 当p、q 第一次相遇时，假设其相遇于结点I，设结点I距离入口结点G的距离为 d，则此时快指针p移动了 2x = a + d + mR (m为整数)、慢指针q移动了 x = a + d + nR (n为整数)；

3. 易得 a + d = (m - 2n)R；

4. 此时将快指针p重新指向链表首结点，让 p、q 同速运动，则当p再次移动a距离后，p指针移动的距离为 a ，q指针移动的距离为 a + d + nR + a = a + (m - n)R = a + kR(k为整数)；易知此时 p、q 重新相遇且相遇结点即为链表环入口结点；

代码实现：

ListNode *detectCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
        return nullptr; // 没有循环
    }
    ListNode *p(head->next->next), *q(head->next);
    while (p != q) {
        if (p == nullptr || p->next == nullptr) {
            return nullptr; // 没有循环
        }
        p = p->next->next;
        q = q->next;
    }
 
    // 找到循环，将快指针p移到头节点
    p = head;
    while (p != q) {
        p = p->next;
        q = q->next;
    }
 
    // p和q现在相遇于环的入口
    return p;
}