描述

示例

思路

一个直观的想法就是用哈希表存下我们从链表头往下走路径所见过的节点指针，当出现已经记录过的节点时，这个节点就是环的入口节点，c++中哈希表可以用stl中的unorder_set()函数，具体学习见C++常用语法——unordered_set。

unordered_set

unordered_set 容器，可直译为“无序 set 容器”。即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。

unordered_set的几个特性：

• 不再以键值对的形式存储数据，而是直接存储数据的值 ；
• 容器内部存储的各个元素的值都互不相等，且不能被修改；
• 不会对内部存储的数据进行排序。

代码

class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_set<ListNode*> st;    // 哈希集合
        while (pHead) {
            if (st.count(pHead)) return pHead;   // 若已经记录过，直接返回
            st.insert(pHead);    // 记录当前结点
            pHead = pHead->next;
        }
        return nullptr;    // 无环
    }
};