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

/*
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode (int x)
    {
        val = x;
    }
}*/
//设两个指针，一个快一个慢，快指针的速度是慢指针的两倍
//设头节点到入口的距离为X，入口到指针相遇的距离为Y，Y是圆环的一部分，Z是Y在圆环的补集，也就是说圆周长Y+Z
//则到达相遇点时，慢指针的路程为 X+Y
//而快指针此时的路程为 2*（X+Y）
//有等式 2*（X+Y）=X+Y+Z+Y
//得 X=Z
//所以我们现让快慢指针相遇
//相遇后再把快指针放到头节点，速度调整为相同的速度重新走
//这样从头开始的快慢指针恰好就相遇在入口节点了
class Solution
{
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead==null)return null;
        // write code here
        ListNode slow=pHead;
        ListNode fast=pHead;

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