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

比较固定的解法。先判定给定链表是否有环，若有则进而找环入口。
使用快慢指针来判断链表是否有环。两指针都从头结点开始，快指针一次走两步，慢指针一次走一步，若两指针相遇，则有环，若其中一个指针为null，则无环。
当链表中有环时，将两指针的其中一个指向头结点，另一指针继续指向相遇结点，然后两指针每次走一步，最终必定在环入口结点处相遇。
这个结论是通过数学证明得到的，感兴趣的朋友可以自己尝试。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        bool hasRing = false;
        if(fast->next && slow->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        while(fast->next && slow->next && fast->next->next){
            if(fast == slow){
                hasRing = true;
                break;
            }
            fast = fast->next->next;
            slow = slow->next;
        }
        if(hasRing){
            fast = pHead;
            while(hasRing){
                if(fast == slow){
                    return fast;
                }
                fast = fast->next;
                slow = slow->next;
            }
        }
        return nullptr;
    }
};