每天一道剑指offer-链表中环的入口结点

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

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

    boolean flag = true;
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null)
            return null;
        ListNode pNode = judgeHasChain(pHead);//判断是否有环
        if(pNode != null)
        {
            int lengthChain = 1;
            ListNode pNodeCopy = pNode.next;
            while(pNodeCopy != pNode)
            {//这个节点已经在环里面了！
                lengthChain++;
                pNodeCopy = pNodeCopy.next;//计算环的长度
            }
            ListNode fast = pHead;
            ListNode slow = pHead;
            int temp = 0;
            while(temp < lengthChain)
            {//快指针先走环的长度
                fast = fast.next;
                temp++;
            }
            while(fast != slow)
            {//快慢指针一起走，因为快指针先走了环长度，当慢指针刚一进环，由于快指针刚好多走了环长度，所以快指针整好走了一个环的周期呀，所以快指针必然也在环的入口
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }
    private ListNode judgeHasChain(ListNode pHead)
    {
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while(fast != slow)
        {
            if(fast != null && fast.next != null)
            {//快指针走一步
                fast = fast.next;
            }else{
                flag = false;
                break;
            }
            if(slow != null && slow.next != null)
            {//慢指针走一步
                slow = slow.next;
            }else{
                flag = false;
                break;
            }
            if(fast == slow)
            {//两者相等，说明相遇了，有环
                return fast;
            }else{
                fast = fast.next;//快指针多走一步
            }
        }
        if(flag)
            return fast;
        return null;
    }
}