链表(四)——判断链表入环点

LeetCode_142_LinkedListCycleII

题目分析：

一开始用上一题的方法快慢指针，相遇后，
任选一个指针回到head，然后都每次走1步，相遇点一定是入环点。
假设入环之前走的距离为x 入环后相遇点到入环点距离为y 环长度为z。
由于快慢指针每次分别走1步和2步。
且相遇时显然
慢指针走了 x + y 距离
快指针走了 x + y + n * z距离 n >=1 的整数
显然
2 * (x + y) = x + y + n * z
=> x = n * z - y
所以在相遇点时，其中一个指针a从头走起，另一个指针b从相遇点继续走，每次都走1步。
根据上方等式。
当从a指针走了x步的时候，b指针必然走了n * z - y步。
x步必然导致a指针在入环点上。
n * z - y 步也必然导致b指针正好在入环点上。
固一定在入环点相遇！！！

解法：

public static ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (null != fast && null != fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (null == fast || null == fast.next) return null;
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return fast;
}