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

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow=pHead;
        ListNode fast=pHead;
        while(true){
            slow=slow.next;
            fast=fast.next;
            if(fast==null)return null;
            else{
                fast=fast.next;
                if(fast==null)return null;
                else if(fast==slow){
                    ListNode p=pHead;
                    while(p!=fast){
                        p=p.next;
                        fast=fast.next;
                    }
                    return p;
                }
            }
        }
    }
}

问题本质上是追及问题

使用快慢指针，我设快指针速度为2，慢指针速度为1，跑道由一段x长的直道和q长的环形跑道组成，快慢相遇时，经过t秒

可得

2*t=x+n*q n=快指针跑的圈数

1*t=x+n2*q n2=慢指针跑的圈数

2*t-1*t=(n-n2)*q 其中n-n2=1，故两者相遇时花的时间步，就是跑道的长度

而 t=x+m m=慢指针此时在一个圈内走的长度

故 t-m=x，也就是说，慢指针再走x步，就能来到环形跑道起点

而注意到，直道长度也是x,也就是说，如果此时，直道上有一个和慢指针速度一样的指针，两者此时同时前进时，一定会在环形跑道起点相遇，因为问题得解