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

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) {
        // 左程云老师讲过这道题，采用快慢指针，快指针一次走两个结点，慢指针一次走一个结点，若二者能相遇，则有环，否则无环
        // 若有环，在快慢指针相遇之后，令快指针返回head，降速成一次走一个结点，当二者再次相遇的结点就是成环结点

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.先判断链表为空的情况
        if (pHead == null) {
            return null;
        }

        // 2.确定链表不为空
        ListNode fast = pHead;
        ListNode slow = pHead;
        boolean hasCycle = false;
        // 注意！这里不能用while而应该用do while
        // 因为fast和slow初始化就是相同的，用while会直接跳出循环
        do {
            // 3.如果链表是无环的，那么fast一定先走到null，直接return false即可
            if (fast.next == null || fast.next.next == null) {
                // 这里一定不会报空指针异常，因为先判断fast.next == null，若满足，则直接return false，不会继续判断后面
                return null;
            }
            // 4.快指针一次走两个结点，慢指针一次走一个结点
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != slow);

        // 5.若因为fast == slow而结束循环，说明fast和slow二者相遇了，说明链表有环
        // 若有环，则令快指针返回head，降速成一次走一个结点，当二者再次相遇的结点就是成环结点
        fast = pHead;
        // 注意！这里不能用do while而应该用while
        // 假如成环结点就是pHead，用do while会错过一次判断
        while (fast != slow) {
            // 6.快指针降速为一次走一个结点，慢指针依然是一次走一个结点
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}