链表中环的入口结点【Java版】

ps：题目不给修改val的值。（如果可以修改的话，直接在val标记就好）

方法一：双指针法（快指针2倍速） [最优解，证明是难点]

上图分析如下：

如果慢指针slow第一次走到了B点处，距离C点处还有距离Y，那么fast指针应该停留在D点处，且BD距离为Y（图中所示是假设快指针走了一圈就相遇，为了便于分析），也就是DB+BC=2Y，（因为fast一次走2步，慢指针一次走1步，并且相遇在C处）
在C点处，此时慢指针slow走的点为ABC，距离为X+Y，而快指针fast走的点为ABCDBC，距离为2X+2Y，
又因为：AB=X，BC=Y，快指针走了2次BC，所以CDB距离为X，而AB距离也为X。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(true){
            if(fast == null || fast.next == null)return null;//退出条件1：无环，fast走到null
            fast = fast.next.next;//fast二倍速
            slow = slow.next;//fast的判空已经覆盖了slow; slow不需要单独判空
            if(fast == slow)break;//退出条件2：有环相遇时
        }
        ListNode front = fast;//front从fast==slow位置、一倍速
        ListNode back = pHead;//back从头开始、一倍速
        while(back != front){
            back = back.next;
            front = front.next;
        }
        return front;//front==back
    }
}//时间O(n)空间O(1)

//构思巧妙，但复现不难。
//过程是这样的：双指针，fast每次走两步，slow每次走一步；
//第一阶段，fast在前，slow在后，如果fast追上slow，说明有环。若fast走到null说明无环。
//第二阶段，back从头开始; front从fast==slow位置开始。现在front和back同速，恰巧可以在入口节点相遇。分析如上图【难点】

方法二：哈希法

import java.util.HashSet;//HashSet的查找时间是O(1),比用ArrayList的O(n)时间好

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        //建立哈希表：存储、查找node //哈希表的特点：便于按值查找；但浪费空间，且易碰撞、无法排序
        while(pHead != null){
            if(set.contains(pHead))return pHead;//有重复，就说明是环入口 //可以证明，单链最多一个环
            else{
                set.add(pHead);
                pHead = pHead.next;
            }
        }
        return null;//无环单链
    }
}//时间O(n) 空间O(n)
//如果用ArrayList的STL那么时间复杂度变为O(n^2)