142. 环形链表 II：结合141与160，快慢指针数学证明 + 算法实现，重点是数学推导.md

题目简述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

题目链接：142. 环形链表 II

哈希表

要做重复检验当然可以考虑哈希表了，只是存在额外的空间开销，但也是一种方法，空间复杂度为 $O(N)$。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */


public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode curr = head;
        while (curr != null) {
            if (set.contains(curr)) return curr;
            set.add(curr);
            curr = curr.next;
        }
        return null;
    }
}

双指针

还是那句话，既然看到链表了，那一定要考虑双指针。事实上，双指针可以只使用 $O(1)$ 的额外空间。这个问题的双指针应用我认为是同时结合了141. 环形链表的快慢指针检测环与160. 相交链表对拓扑结构的巧妙利用，在步骤上也很像融合了两者。和160. 相交链表一样地，我们先说明应该怎么做，再证明这样做的合理性。

• 首先用快慢指针检测环路，如果不存在直接返回 null；
• 如果存在环路，则在检查出环路时在标头重新放置一个慢指针（原有慢满指针继续自增，但快指针我们已经不需要了），那么下一次两个慢指针相遇时的位置即为环路起始节点。

假设非环路部分长 $\text{len}A$、环路部分长 $\text{len}B$，节点的索引从0开始计数，则环路起始节点的索引为 $\text{len}A$。快慢指针起始时都位于表头（表头节点索引为 $0$），快指针每次自增 $2$、慢指针每次自增 $1$。

首先证明为何如果存在环路则快慢指针必然能够相遇。假设慢指针走过了 $n$ 步，则快指针走过了 $2n$ 步，记环路起始节点在环路中的位置为 $0$、在环路中起始节点的前继节点位置为 $\text{len}B-1$，那么慢指针在环路中的位置是 $(n-\text{len}A)\ %\ \text{len}B$、快指针在环路中的位置是 $(2n-\text{len}A)\ %\ \text{len}B$——如果这部分弄不清楚是否要在何处加减 $1$ 可以画一个图举一个例子帮助推导一下。是否存在 $n^{\ast}$，使得 $(n^{\ast}-\text{len}A)\equiv(2n^{\ast}-\text{len}A)\ \ (\mathrm{mod}\ ,,\text{len}B)$ 呢？

根据同余的性质， $$ \begin{align} &\ \ \ \ \ \ (n^{\ast}-\text{len}A)\equiv(2n^{\ast}-\text{len}A)\ \ (\mathrm{mod}\ ,,\text{len}B)\ &\Leftrightarrow n^{\ast}\equiv 2n^{\ast}\ \ (\mathrm{mod}\ ,,\text{len}B)\ &\Leftrightarrow n^{\ast}\equiv 0\ \ (\mathrm{mod}\ ,,\text{len}B)\ \end{align} $$ 因此必然存在这样的 $n^{\ast}$ 使得快慢指针相遇！并且容易知道 $n^{\ast}=k\cdot\text{len}B$，这里 $k\in N$ ，同时约束 $n^{\ast}\geqslant\text{len}A$——这是为了保证快慢指针至少已经都进入了环路。

接下来证明为什么当 $n=n^{\ast}$ 时，我们在表头处再放置一个慢指针后，两个慢指针第一次相遇时所处的节点一定是环路起始节点。实际上，这就是要证明当 $n=n^{\ast}$，必然有 $\big[(n-\text{len}A)+\text{len}A\big]\ %\ \text{len}B=0$——根据 $n^{\ast}$ 的定义，这不是显而易见吗？！ $$ \begin{align} &\ \ \ \ \ \ \big[(n^{\ast}-\text{len}A)+\text{len}A\big]\ %\ \text{len}B\ &=,n^{\ast}\ %\ \text{len}B\ &=,0\ %\ \text{len}B\ &=,0 \end{align} $$ 证明不难，算法的设计更不难，本问题的难点在于如何想到我们需要这样子证明、这样子设计。

接下来，程序是很容易编写的了。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode temp = head;
                while (temp != slow) {
                    temp = temp.next;
                    slow = slow.next;
                }
                return temp;
            }
        }
        return null;
    }
}