142.环形链表II

题目

142.环形链表II

要求

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

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

不允许修改 链表。

思考答案

这道题目可以借用哈希表来实现，一边遍历，一边放入哈希，直到哈希中存在当前遍历的节点或者遍历到末尾结束，代码如下：

public ListNode detectCycle(ListNode head) {
    ListNode virtual = head;
    HashMap<ListNode, Integer> map = new HashMap<>();
    int index = 0;
    while (virtual != null) {
        if (map.get(virtual) != null) {
            return virtual;
        }
        map.put(virtual, index ++);
        virtual = virtual.next;
    }
    return null;
}

接下来说说快慢指针的思路，快慢指针判断环这个简单理解，借用时钟来举例，一个从 12 出发，一个从 6 出来，从 6 出发的每次都两个小时，就是

6 → 8 → 10 → 12 → 2 → 4 → 6 ·····，

12 出发的路径如下：

12 → 1 → 2 → 3 → 4 → 5 → 6 -> 7 → 8，在 6 相遇了，这道题目的难点不在这，在一个数学计算，看下图：

这里直接借用了 leetcode 上的图，slow 走的距离是 a + b，主要 slow 进入环，则在 slow 走到 a 和 b 的相交点前，fast 和 slow 一定会相遇，假设在紫色点相遇，这个时候 fast 走的举例是 a + n(b + c) + b，因为 slow 每次走一步，fast 每次走两步，所以得到公式 a + n(b + c) + b = 2 (a + b)，经过换算，可以得到 a = (n - 1) b + nc，这里其实看不出什么规律，换算一下a = (n - 1) b + (n - 1)c + c，换算得到 a = (n - 1) (b + c) + c，也就是说 slow 从紫色点出发，另外一个节点从 a 开始出发，则一定会在 a 和 b 的相交点相遇，否则公式不成立。所以最后的代码如下：

public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (slow != null && fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
						// 数学公式推到的结论
            ListNode pre = head;
            while (pre != slow) {
                pre = pre.next;
                slow = slow.next;
            }
            return slow;
        }
    }
    return null;
}