链表中环的入口结点

以前看过忘了解法，以至于没有思路，这道题目的前置题目是如何判断链表中有环，想了双指针，发现只能判断链表中是否有环，判断不了环的起点。

哈希表解法，这个解法的前提是链表中不存在值相同的节点，但是题目中并没有这样的表述，因此不认为这个解法有价值。

数学解法，先通过快慢指针判断是否有环，如果有环，则让头指针和慢指针同时走，二者相遇的地方就是环的入口，这个想法实现很简单，但是需要数学的推导证明头指针走到环起点的步数正好是慢指针走到环起点的步数，老实说我是没有想出来。

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

《剑指Offer》书上的解法相对于上面的推导要简单一些：

1. 判断是否有环的标准动作
2. 如果有环，统计环中的节点个数，从环中的任何一点出发，一次一步再走回到自己的步数
3. 两个指针都指向头，一个提前走环的个数步，然后两个指针一起向前一次一步同时走，二者相遇的位置就是环的起点。

对比数学推导，思路相对好理解一些，前指针比后指针早走了环的大小，当后指针走到环的起点时，前指针刚好比它多走了一圈，正好回到环的起点。这个解法虽然摆出来相对好理解，但是让解题人去想还是需要技巧的。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode head) {
        if (head == null || head.next == null)
            return null;
        // 双指针判断链表中是否有环，基操勿6
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow)
                break;
        }
        if (fast == null) // 无环
            return null;

        // 统计环中的个数
        fast = slow;
        int count = 1;
        while(fast.next != slow) {
            fast = fast.next;
            ++count;
        }

        // 准备前后指针，前指针先走环的个数步
        fast = head;
        slow = head;
        while (count-- > 0) {
            fast = fast.next;
        }

        // 前后指针同时走，相遇处就是环的起点
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}