題目：
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?
給定一個(gè)鏈接列表，返回循環(huán)開始的節(jié)點(diǎn)。如果沒有循環(huán)，則返回NULL。
拓展：
你能在不占用額外空間的情況下解決這個(gè)問題嗎？

思路：
快慢兩個(gè)指針，先判斷是否有環(huán)，沒有返回null，有的話，快慢兩個(gè)指針會(huì)相遇
然后兩指針分別從頭和從相遇點(diǎn)出發(fā)，再次相遇即為環(huán)入口點(diǎn)

至于為什么：

image.png

證明如下：
如上圖所示，X,Y,Z分別為鏈表起始位置、環(huán)開始位置和兩指針相遇位置，則根據(jù)快指針?biāo)俣葹槁羔標(biāo)俣鹊膬杀叮梢缘贸觯?br> 2 * (a + b) = a + b + n * (b + c)；即
a = (n - 1) * b + n * c = (n - 1) * (b + c) + c;
注意到b + c恰好為環(huán)的長(zhǎng)度，故可以推出，如將此時(shí)兩指針分別放在起始位置和相遇位置，并以相同速度前進(jìn)，當(dāng)一個(gè)指針走完距離a時(shí)，另一個(gè)指針恰好走出 繞環(huán)n-1圈加上c的距離。
故兩指針會(huì)在環(huán)開始位置相遇。

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;
    }
}