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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
         //1.空间复杂度O（n）的set\hash法：遍历链表，记录节点地址是否出现过，若出现重复，则为入口节点；
        if(pHead==nullptr){
            return nullptr;
        }
        //HASH表实现、不会自动排序、增删查复杂度为O(1)
        unordered_set<ListNode*> MySet;
        for(ListNode *front = pHead; front!=nullptr; front = front->next){
            if(MySet.find(front)==MySet.end()){
                MySet.insert(front);
            }else{
                return front;
            }
        }
        return nullptr;

        //2.双指针：以下代码仅判断是否有环；
        //官方题解中具体推导环入口位置
        //https://blog.nowcoder.net/n/f80b6497aaa944ae9aadfb7307467d4e
        // for(ListNode *front = pHead->next, *behind = pHead; front!=nullptr;){
        //     if(front == behind){
        //         return front;
        //     }
        //     if(front->next == nullptr){
        //         return nullptr;
        //     }
        //     front = front->next->next;
        //     behind = behind->next;
        // }
        // return nullptr;
    }
};