leetcode--09. 链表环起点 II

题目：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
给定一个链接列表，返回循环开始的节点。如果没有循环，则返回NULL。
拓展：
你能在不占用额外空间的情况下解决这个问题吗？

思路：
快慢两个指针，先判断是否有环，没有返回null，有的话，快慢两个指针会相遇
然后两指针分别从头和从相遇点出发，再次相遇即为环入口点

至于为什么：

image.png

证明如下：
如上图所示，X,Y,Z分别为链表起始位置、环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出：
2 * (a + b) = a + b + n * (b + c)；即
a = (n - 1) * b + n * c = (n - 1) * (b + c) + c;
注意到b + c恰好为环的长度，故可以推出，如将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。
故两指针会在环开始位置相遇。

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