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

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

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



    //左神讲的
    //先说个定理：两个指针一个fast、一个slow同时从一个链表的头部出发
    //fast一次走2步，slow一次走一步，如果该链表有环，两个指针必然在环内相遇
    //此时只需要把其中的一个指针重新指向链表头部，另一个不变（还在环内），
    //这次两个指针一次走一步，相遇的地方就是入口节点。
    //这个定理可以自己去网上看看证明。
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null){
            return null;
        }

        ListNode slowNode = pHead;
        ListNode fastNode = pHead;
        while(fastNode!=null && fastNode.next!=null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            if(slowNode == fastNode){
                break;
            }
        }

        //无环
        if(fastNode==null || fastNode.next==null){
            return null;
        }

        //让其中一个指针 重新指向头节点 速度都为1
        fastNode = pHead;
        while(fastNode!=slowNode){
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }

        return fastNode;
    }
}