链表中环的入口结点 【空间复杂度O（1）】

题目：

给一个链表，若其中包含环，则返回环的入口结点，否则返回null。

思路：

思路一：

遍历整个链表，将链表中的每个结点都存在哈希表中，如果遇到重复结点，那这个结点就是环的入口结点。时间复杂度和空间复杂度都是O(n)。

思路二：

快慢指针法，通过一个快指针和一个慢指针遍历整个链表，如果两个指针相遇，则说明链表中有环。

知道有环之后，应该怎么快速找到环的入口呢？如下图所示：

假设黄色路线是慢指针走过的路径，红色路线是快指针走过的路径，由于快指针速度是慢指针的二倍，所以通过简单的化简就能得到环中慢指针未走的长度刚好是环外部分的长度！所以再安排一个指针从起点出发，这个新指针与慢指针相遇的位置刚好就是环的入口。（上图中的直线与环的长度刚好合适，如果某个部分过长，可能会绕几圈再相遇，结论依然是一样的）这种方法的时间复杂度依然是O(n)，空间复杂度降为了O(1)。

代码：

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead){

        ListNode f = pHead;

        ListNode s = pHead;

        if (pHead==null||pHead.next == null) return null;

        do{

            f = f.next.next;

            s = s.next;

        }while(f!=null&&f.next!=null&&f!=s);

        if (f==null||f.next == null) return null;

        ListNode ns = pHead;

        while (ns!=s){

            ns = ns.next;

            s = s.next;

        }

        return ns;

    }

}