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

方法一：对于链表中环的入口结点来说有什么特点，如果遍历整个链表，那么第二次出现的节点也就是此入口节点。那么不妨用一个哈希表来记录链表，然后循环链表，每次遍历到某个节点的时候判断是否在哈希表中出现过。如果未出现，那么记录下来，继续循环。如果出现过，那么这就是入口节点，直接返回即可。 代码：

public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_map<ListNode*, int> mp;
        ListNode* head = pHead;
        while(head != nullptr){
            if(mp.find(head) == mp.end()){
                mp[head] = 1;
                head = head->next;
            } else {
                return head;
            }
        }
        return nullptr;
    }
};

方法二：快慢指针，这个还真不好想到。就是利用路程相等的思想，来控制fast指针和low指针走的速度。具体思路就是先让fast指针每次走两步，low指针每次走一步。那么两个指针一定会在环中某个节点相遇，然后相遇后，让fast指针再次指向head节点。然后再fast和low指针每次走一步，两指针再次相遇就是入口节点。整体思路还是比较简单，但是 个人感觉比较坑的地方就是要处理好无环的情况。