链表找出环的入口

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。
你是否可以不用额外空间解决此题？

https://leetcode-cn.com/problems/linked-list-cycle-ii/description/

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) {
                slow = head;
                while(fast != slow ){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

说明：

1. 定义两个指针，快指针每次走两步，慢指针一次走一步，当环存在时，则快指针一定会追上慢指针；
2. 追上时使其中一个指针指向链头，然后两个指针同时走，则再次相遇时指针的位置为环开始的位置

？？？

为什么快指针一定会追上慢指针？

快指针F 比慢指针S 先进环，假设进环时F离S还差a, S 走b步后F追上，则

2b (F走的距离) = b + a （S走的距离+原来的差距）

即b=a，当S进环时，F离S多远则再过多少步可以追上。

想起小学奥数，甲和乙在夕阳下的奔跑。（追逐问题）

为什么快指针在慢指针走完环一圈之内追上？

假设F,S同时入环，则第一次相遇时，F刚好走两圈，而S刚好走1圈，即F追了S一圈。

而题目条件，F比S先或同时入环（环入口为在链头时，同时入环），则F需要追S的距离小于一圈，即追的过程中，S走的距离<=一圈

为什么第二次追上后的点为入环节点？

假设链表为

1->2->3->...->m->...->n->m
//链表长度为n,m为入环点。则有1<=m<=n

第一次追上时花费时间为x

1+x = 1+2x-(n-m+1) //慢指针所在的位置 = 快指针所在位置 (快指针走的距离-环的长度)

得出：

x = (n-m+1); //环的长度

第二次，S从头开始，F从当前相遇位置开始，同时以一步的速度走。则，S走到m位置需要m-1步; 而F走了m-1步后为：

1+2x-(n-m+1) + m-1 => (n-m+1) + m => n+1 => n的下一个位置即为环的开始m

问题得证。