链表中换环的入口节点C++实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead==NULL){
            return NULL;
        }
        
        ListNode* fast=pHead;
        ListNode* slow=pHead;
        
        while((fast->next!=NULL)&&(fast!=NULL)){//？？？
                        
            fast=fast->next->next;
            slow=slow->next;
            
            if(fast==slow){
                //return slow;
                //注意第一次相遇时并非一定是在环的入口，可能在环内的任何地方
                fast=pHead;
                while(fast!=slow){
                    fast=fast->next;
                    slow=slow->next;
                }
                return slow;
            }
        }
        
        return NULL;
    }
};

注意：

1. 第一次相遇时并非一定是在环的入口，可能在环内的任何地方，所以直接返回第一次相遇节点是错误的。
2. 为啥第一次相遇后再将快指针指向开头，然后等速步进就能在入口相遇？ 关键在于快指针是满指针的2倍速，注意在判断是否有环中，这个倍数可以随便设，但找入口节点就不行，因为二倍速决定了第一次相遇时，传达出了两个信息： 1）快指针比满指针多跑一圈，这个画图就知道。 2）快指针走的路程是慢指针的一倍。 所以可知， 算了，TMD，直接背下来