链表中环的入口结点

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

快慢指针，有环必相遇。设环长c，环外长d，自环外起点，从0开始编号，环内自入口从0开始编号。

二者第一次相遇，快指针走了$2n_1$步，慢指针走了$n_1$步，相遇即$(2n_1 - d) \% c = (n_1 - d) \% c$，即$n_1 \% c = 0$。

此时将慢指针置回起点，二者同速各走$n_2 = d$步，慢指针在入口，快指针在$(2n_1 + n_2 - d) \% c = 2n_1 \% c = 0$处，即二者在入口处相遇。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (pHead == nullptr)
        {
            return nullptr;
        }
        else if (pHead->next == pHead)
        {
            return pHead;
        }
        else
        {
            ListNode *f = pHead, *s = pHead;
            while (f == pHead || f != s)
            {
                s = s->next;
                f = f->next;
                if (f == nullptr)
                {
                    return nullptr;
                }
                else
                {
                    f = f->next;
                }
                if (f == nullptr || s == nullptr)
                {
                    return nullptr;
                }
            }
            s = pHead;
            while (f != s)
            {
                f = f->next;
                s = s->next;
            }
            return f;
        }
    }
};