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

import java.util.*;
/*
判断链表是否有环。 (如果有环，环没有null节点，因此快慢指针一定会相遇)


*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 先找到快慢指针相遇点
        ListNode fast = pHead;
        ListNode slow = pHead;

        //找到快慢指针相遇点
        ListNode meetNode = FindMeetPoint(fast, slow);

        //相遇点不为null说明相遇了，
        //快指针从头结点开始，慢指针从相遇点开始。
        if (meetNode != null) {
            fast = pHead;
            slow = meetNode;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            //再次相遇，找到入口节点，返回
            return slow;
        } else {
            return null;
        }
    }

    public ListNode FindMeetPoint(ListNode fast, ListNode slow) {
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return slow;
            }

        }
        return null;

    }
}