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

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) {
        if(pHead == null || pHead.next  == null){
            return null;
        }
        ListNode p = pHead;
        ListNode slow = pHead;
        ListNode fast = pHead;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                while(p != slow){
                    p = p.next;
                slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }
}

从head到环的入口加上入口到slow的距离是环的长度的整数倍 然后让一个节点从head移动 slow继续转圈 从head转到环的入口刚好slow就完整的绕了n圈回到环的入口