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

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

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode meet = firstMeet(pHead);

        //没有环
        if (meet == null) {
            return null;
        }

        //快慢指针首次相遇点 和 头结点分别按相同速度出发，再次相遇即入口节点
        ListNode h = pHead;
        //执行到这肯定成环，因此h meet 不会为null
        while (h.val != meet.val) {
            h = h.next;
            meet = meet.next;
        }
        return h;
    }

    public ListNode firstMeet(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            //快指针遍历到头，证明没有成环
            if (fast == null) {
                return null;
            }

            //快指针追上慢指针，证明成环
            if (slow.val == fast.val) {
                return slow;
            }
        }

        return null;
    }
}