Linked List Cycle II

    1. 每次相遇都在同一个节点。第一次相遇至第二次相遇，快指针需要比慢指针多走一个环的节点个数，而快指针比慢指针多走的步数正好是慢指针自身移动的步数，故慢指针恰好走了一圈回到原点。

    从以上两个容易得到的特性可知，在仅仅知道第一次相遇时的节点还不够，相遇后如果不改变既有策略则必然找不到环的入口。接下来我们分析下如何从第一次相遇的节点走到环的入口节点。还是让我们先从实际例子出发，以下图为例。

    和fast节点分别初始化为节点1和，假设快慢指针第一次相遇的节点为0, 对应于环中的第i个节点 C_i, 那么此时慢指针正好走了 n - r - 1 + i 步，快指针则走了 2 \cdot (n - r - 1 + i) 步，且存在[^1]: n - r - 1 + i + 1= l \cdot r. (之所以在后面加1是因为快指针初始化时多走了一步) 快慢指针第一次相遇时慢指针肯定没有走完整个环，且慢指针走的步数即为整数个环节点个数，由性质1和性质2可联合推出。

    1. 异常处理。
    2. 找第一次相遇的节点。
    3. 将fast置为头节点，并只走一步，直至快慢指针第二次相遇，返回慢指针所指的节点。

    第一次相遇的最坏时间复杂度为 O(n), 第二次相遇的最坏时间复杂度为 O(n). 故总的时间复杂度近似为 O(n), 空间复杂度 O(1).