环形链表II

来自Leetcode第142题环形链表II

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。
示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

哈希

思路同141环形链表，用一个set来判断，如果有重复的，直接返回该元素即可。

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next == null)
        return null;
    Set<ListNode> map = new HashSet<>();
    while (head != null){
        if(map.contains(head))
            return head;
        else{
            map.add(head);
            head = head.next;
        }
    }
    return null;
}

双指针

这题有个坑，和上一题不一样。
上一题条件宽松，在环里相遇即可，并且对初始步数无要求。
我在复用上一题代码时，因为初始步数的不一致，导致了最终在死循环里出不来。代码块里注释部分就是导致死循环的地方，尽管两个都能判断相遇成环，但是相遇点不一样，就为后来的找环入口算法带来了障碍。
或者注释部分用最开始的双指针代替也可。

数学解释：

从 head 到入口点的距离设为 x，入口点到相遇点的距离设为 y，环的的长度设为 n。
假设 slow 指针走过的距离为 t，那么 fast 指针走过的一定是 slow 指针的 2 倍，也就是 2t。
slow 指针从 head 出发走了 x 的距离到达入口点，然后可能走了 k1 圈，然后再次回到入口点，再走了 y 的距离到达相遇点和 fast 指针相遇。
t = x + k1 n + y
fast 指针同理，fast 指针从 head 出发走了 x 的距离到达入口点，然后可能走了 k2 圈，然后再次回到入口点，再走了 y 的距离到达相遇点和 slow 指针相遇。
2t = x + k2 n + y
上边两个等式做一个差，可以得到
t = (k2 - k1) n
设 k = k2 - k1 ，那么 t = k n。
把 t = k n 代入到第一个式子 t = x + k1 n + y 中。
k n = x + k1 n + y
移项，x = (k - k1) n - y
取出一个 n 和 y 结合，x = (k - k1 - 1) n + (n - y)
左边的含义就是从 head 到达入口点。
右边的含义， n - y 就是从相遇点到入口点的距离，(k - k1 - 1) * n 就是转 (k - k1 - 1) 圈。
左边右边的含义结合起来就是，从相遇点走到入口点，然后转 (k - k1 - 1) 圈后再次回到入口点的这段时间，刚好就等于从 head 走向入口点的时间。
所以代码的话，我们只需要 meet 指针从相遇点出发的同时，让 head 指针也出发， head 指针和 meet 指针相遇的位置就是入口点了。

假设非环部分的长度是x，从环起点到相遇点的长度是y。环的长度是c。
现在走的慢的那个指针走过的长度肯定是x+n1*c+y，走的快的那个指针的速度是走的慢的那个指针速度的两倍。这意味着走的快的那个指针走的长度是2(x+n1*c+y)。

还有一个约束就是走的快的那个指针比走的慢的那个指针多走的路程一定是环长度的整数倍。根据上面那个式子可以知道2(x+n1*c+y)-x+n1*c+y=x+n1*c+y=n2*c。

所以有x+y=(n2-n1)*c,这意味着什么？我们解读下这个数学公式：非环部分的长度+环起点到相遇点之间的长度就是环的整数倍。这在数据结构上的意义是什么？现在我们知道两个指针都在离环起点距离是y的那个相遇点，而现在x+y是环长度的整数倍，这意味着他们从相遇点再走x距离就刚刚走了很多圈，这意味着他们如果从相遇点再走x就到了起点。
那怎么才能再走x步呢？答：让一个指针从头部开始走，另一个指针从相遇点走，等这两个指针相遇那就走了x步此时就是环的起点。

通过上面的数学解释，在回顾最开始的代码，就知道了原因所在。最开始就异步，两个指针的步数不一致，也就破坏了后续的推导证明。

public static ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    /*ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
        if(fast == slow)
            break;
    }*/
    ListNode fast = head, slow = head;
    while (true) {
        if (fast == null || fast.next == null) return null;
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    //这时候已经相遇
    fast = head;
    while (slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    return fast;
}