剑指offer---链表中环的入口结点

题目：链表中环的入口结点

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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {

    }
};

解题代码：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead == nullptr)
            return nullptr;
        // 判断链表是否有环
        // 若含有环，则返回环中某个节点的地址
        // 否则，返回nullptr
        ListNode* temp = mergeNode(pHead);
        if(temp == nullptr)
            return nullptr;
        // 求解环中含有几个节点
        ListNode* start = temp->next;
        int count = 1;
        while(start != temp){
            start = start->next;
            count++;
        }
        //寻找环的入口节点
        ListNode* p1 = pHead;
        ListNode* p2 = pHead;
        // 先移动p1
        for(int i = 0; i < count; i++)
            p1 = p1->next;
        // p1, p2 一起移动
        while(p1 != p2){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
private:
    ListNode* mergeNode(ListNode* pHead){
        ListNode* slow = pHead->next;
        if(slow == nullptr)
            return nullptr;
        ListNode* fast = slow->next;
        while (fast != nullptr) {
            if(slow == fast)
                return fast;

            slow=slow->next;
            fast=fast->next;

            if(fast != nullptr && fast != slow)
                fast=fast->next;
        }
        return nullptr;
    }
};