题解 | #链表中环的入口结点#

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow1 = hasCycle(pHead);
        //神奇的算法：
        //当找到快慢指针第一次相遇的节点后，保存在slow1
        //创建出新的慢指针slow2,当两个指针再次相遇就是入口！！！
        //这是什么道理？是质子吗？？？ 为什么不会错过？我试了很多次都是的，好魔幻啊！！！
        if(slow1!=null){
            ListNode slow2 = pHead;
            while(slow1!=slow2){
                slow1 = slow1.next;
                slow2 = slow2.next;                
            }
            return slow2;
        }
        return slow1;
    }

    public ListNode hasCycle(ListNode pHead){
        if(pHead==null)
        return null;

        //快慢指针
        ListNode slow = pHead;
        ListNode fast = pHead;

        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return slow;
            }
        }
        return null;    
    }
}