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

思路： 如果有环，把这个链表想象成刀，我们从刀把开始出发，刀把长x,假设第一次相遇时走了 x+y ，y是环上的距离。fast则走了2*(x+y), y % s == (2*(x+y) - x) % s ,也就是说 y%s == (x + 2y ) %s,所以x + y == s的，也就是说 slow再走x距离就到了环入口节点。所以将fast节点重置为头结点遍历即可

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

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        /*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
         
        if(pHead == null ||pHead.next == null){
            return null;
        }
        //快慢指针
        //假设入环有M 个元素，环中有N个元素
        //第一次相遇 慢指针走了S ，快指针走了2S， (S - M)%N == （2S -M）%N , 相遇时环中位置index是一样的
        //快指针放到链表头，按慢指针走法  第二次相遇时，画个图就看出来了，或者从上面的列的式子就可以看出 走X=M步 (S-M+X)%N  == 0
        ListNode slow = pHead;
        ListNode fast = pHead;
        boolean isMeet = false;
        while(slow != null && fast!= null){
            
            if(fast.next == null){
                return null;
            }
            if(!isMeet){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    isMeet = true;
                    fast = pHead;
                }
            }else{
                if(slow == fast){
                    return slow;
                }
                slow = slow.next;
                fast = fast.next;
          
            }
          
        }
        
        
        return null;
    }
 
   
}