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

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

        ListNode slow = pHead; //乌龟
        ListNode fast = pHead; //兔子

        //判断是否有环
        while (fast != null && fast.next != null){
            slow = slow.next; //乌龟一步
            fast = fast.next.next;  //兔子两步
            if(slow == fast)
            break;
        }

        //无环  
        if (fast == null || fast.next == null)
        return null;

        //相遇了，兔子一脚给乌龟踢回原点
        slow = pHead;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next; //兔子掉以轻心
        }
        return slow;
    }
}