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

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(null==pHead||null==pHead.next){
            return null;
        }

        //检查环
        ListNode meetingNode=getMeetingNode(pHead);

        if(null==meetingNode){
            return null;
        }

        //找入口
        return findLoopEntry(pHead,meetingNode);
    }

    private ListNode getMeetingNode(ListNode head){
        // 慢指针
        ListNode slow=head;
        // 快指针
        ListNode quick=head;

        while(null!=quick && null!=quick.next){
            // 慢指针走一步
            slow=slow.next;
            // 快指针走2步
            quick=quick.next.next;
            // 相遇
            if(slow==quick){
                return slow;
            }
        }

        return null;
    }

    private ListNode findLoopEntry(ListNode pHead,ListNode meetingNode){
        ListNode pt1=pHead;
        ListNode pt2=meetingNode;
        while (pt1!=pt2){
            pt1=pt1.next;
            pt2=pt2.next;
        }

        return pt1;
    }


}