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

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

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

// 为了保证空间复杂度o(1)，不能使用哈希表

// 那么只剩下双指针，之前采用快慢指针判断出是否存在环

// 现在可以根据其长度来得出快慢指针相遇点与环的关系

// 假设从0到入口长度为x，从入口到相遇点长度为y，慢指针走了x+y，快指针走了2x+2y

// 那么我们可以得出相遇点到入口位置的长度等于0到入口的长度

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        
        // 判断是否存在链表
        if(pHead == null){
            return null;
        }

        // 定义快慢指针
        ListNode fastNode = pHead;
        ListNode slowNode = pHead;

        // 第一次相遇
        while(fastNode != null && slowNode != null){

            // 多一重判断，为了防止fastNode下一个点为null导致错误
            if(fastNode.next == null){
                return null;
            }

            fastNode = fastNode.next.next;
            slowNode = slowNode.next;

            // 第一次相遇跳出循环，即slowNode和fastNode就是相遇点
            if(fastNode == slowNode){
                break;
            }

        }

        // 首先判断是相遇break还是链表null
        if(fastNode == null){
            return null;
        }

        // 正常移动，都1步移动，相遇点极为入口
        slowNode = pHead;
        while(fastNode != slowNode){
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }

        // 跳出循环即为相遇，输出
        return slowNode;

    }
}