题目地址：

https://leetcode.com/problems/linked-list-cycle-ii/

链表求环，如果有环，返回环的入口，否则返回null。

经典快慢指针算法。先用快慢指针判断有没有环，见https://blog.csdn.net/qq_46105170/article/details/104013645，然后重新设一个节点cur等于head，接着cur和slow同时出发，每轮循环走一步，直到相遇。则相遇点即为环的入口。代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    ListNode dummy(0, head);
    auto slow = &dummy, fast = &dummy;
    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast)
        break;
    }
    if (!fast || !fast->next)
      return nullptr;
    slow = &dummy;
    while (slow != fast) {
      slow = slow->next;
      fast = fast->next;
    }
    return slow;
  }
};

时间复杂度$O(n)$。

算法正确性证明：
设链表有环，链表的nodes是这样排列：$$v_1\to v_2\to ...\to v_{k-1}\to v_k\to v_{k+1}\to ...\to v_{k+s}\to v_k$$也就是说从$v_k$到$v_{k+s}$形成一个环，环的边数为$s+1$。我们对于slow和fast各自走了多少步做分析。当slow走到$v_k$时，它走了$k-1$步，而fast走的步数是slow的两倍，所以fast走了$2(k-1)$步，fast所处于的位置的下标是$k+(k-1)\%(s+1)$。设slow再走$x$步就与fast相遇，那么有同余式：$$x\equiv 2x+k-1\mathrm{mod}(s+1)$$所以$$x+k-1\equiv 0\mathrm{mod}(s+1)$$也就是说slow再走$k-1$步就到达了$v_k$，而新的节点cur从head出发同时走$k-1$步正好也会走到$v_k$，所以相遇点就是环的入口。