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

解题思路：

    将任务分解为两部分：（1）判断是否有环；（2）找到环的入口。

首先，我们先利用快慢指针，找到两指针相遇的地方；

然后，将快指针重置为头节点，慢指针置为二者相遇的位置，然后，开始循环，且这一次快慢指针的速度相同。当它们再次相遇时，就是环的入口位置。

代码如下：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    
    //-------------判断是否有环
    ListNode* hasCycle(ListNode* head){
        if(head == nullptr){
//             cout << "pHead is nullptr";
            return nullptr;
        }
        //快慢指针
        ListNode* fast = head;
        ListNode* slow = head;
        //如果没有环，则快指针会先到达链表尾部
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
//                 cout << "there is a cycle.";
                return slow;  //返回相遇的地方
            }
        }
        return nullptr;  //没有环返回空
    }
    //----------计算环的入口位置
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* slow = hasCycle(pHead);
        if(slow == nullptr){ //没有环
//             cout << "slow is nullptr";
            return NULL;
        }
        //快指针回到表头
        ListNode* fast = pHead;
        //再次相遇就是环入口
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        
        return slow;
    }
};