c++实现--链表中环的入口结点

#include<unordered_set>
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        unordered_set<ListNode*> st;
        while(pHead){
            if(st.find(pHead)==st.end()){//当前结点未出现过，加入到链表中
                st.insert(pHead);
                pHead=pHead->next;
            }else{
                return pHead;//已经出现过了，说明当前是环的入口节点
            }
        }
        return nullptr;//否则没有环

    }
};

双指针法
1.初始化：快指针fast指向头结点， 慢指针slow指向头结点
2.让fast一次走两步， slow一次走一步，第一次相遇在C处，停止
3.然后让fast指向头结点，slow原地不动，让后fast，slow每次走一步，当再次相遇，就是入口结点。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //方法二：使用快慢指针
        if(pHead==nullptr){
            return nullptr;
        }
        ListNode* fast=pHead;
        ListNode* slow=pHead;
        while(fast&&fast->next){
            fast=fast->next->next;//快指针一次走两步
            slow=slow->next;//慢指针一次走一步；
            if(slow==fast){//当快慢指针相遇，则退出
                break;
            }
        }
        if(!fast||!fast->next){
            return nullptr;
        }
        fast=pHead;//将fast指针从头结点开始
        while(slow!=fast){//两个指针同步运动，当两个指针相遇时，即为环的入口节点
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};