剑指Offer44-链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
/* 思路： 设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。 接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。以下是两个结论证明： 两个结论： 1、设置快慢指针，假如有环，他们最后一定相遇。 2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。 证明结论1：设置快慢指针fast和low，fast每次走两步，low每次走一步。 假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。 */
public class Solution {
   
 
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
   
        ListNode low=pHead;
        ListNode fast=pHead;
        while(fast!=null&&fast.next!=null){
   
            low=low.next;
            fast=fast.next.next;
            if(low==fast){
   
                break;
            }
        }
        if(fast==null||fast.next==null)
            return null;
        low=pHead;
        while(fast!=low){
   
            low=low.next;
            fast=fast.next;
        }
        return low;
    }
}