快慢指针解决环型链表问题

因为快指针是慢指针的两倍速，且他们在p点相遇，则我们可以得到等式 2(A+B) = A+B+C+B
如果环前面的链表很长，而环短，那么快指针进入环以后可能转了好几圈(假设为n圈)才和慢指针相遇。但无论如何，慢指针在进入环的第一圈的时候就会和快的相遇。等式应更正为 2(A+B)= A+ nB + (n-1)C
因此可得 C = A。

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

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

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast, slow;
        boolean flag = false;
        fast = pHead;
        slow = pHead;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

            //找到相遇点
            if(slow == fast){
                flag = true;
                break;
            }
        }
        //这里进行等式验证过，当slow == fast时就是环的入口
        if(flag){
            slow = pHead;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        return null;
    }
}