题目

思路一 辅助数组遍历链表

思路：遍历链表的过程中记录下链表每个节点的地址，同时对每个节点经检查地址是否与之前节点重复，存在重复即为环入口。

时空复杂度分析：两部分，一部分遍历，记录节点地址，第二部分检查，当前节点数减一。查到环入口节点需要遍历所有节点。时间复杂度为O(n^2)，空间复杂度O（n）。

代码：

#include <vector>
class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        vector<ListNode*> vec;
        for (ListNode* p = pHead; p != nullptr; p = p->next) {
            for (auto e : vec) {
                if (p == e) {
                    return p;
                }
            }
            vec.emplace_back(p);
        }
        return nullptr;
    }
};

思路二 哈希表

思路一开销大头在检查之前节点是否与当前节点地址相同，即查询问题，如果能以节点地址为key快速查找之前节点是否存在重复节点，空间复杂度降为o(n)。（不考虑查询开销）

引入哈希表用于查询

unordered_set

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

总的来说，unordered_set 容器具有以下几个特性：

• 不再以键值对的形式存储数据，而是直接存储数据的值；

容器内部存储的各个元素的值都互不相等，且不能被修改。

不会对内部存储的数据进行排序（这和该容器底层采用哈希表结构存储数据有关，

#include <unordered_map>
class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_set<ListNode *> traversed_nodes;
        ListNode * cur_ptr=pHead;
        while (cur_ptr!=nullptr) {
            if (traversed_nodes.find(cur_ptr)!=traversed_nodes.end())   
            // unordered_set查找，找不到返回end()迭代器
            {
                return cur_ptr;
            }
            else {
                traversed_nodes.insert(cur_ptr);
                cur_ptr=cur_ptr->next;
            }
        }
        return nullptr;
    }
};

思路三 双指针法

抄的，第一次学这个算法

时间复杂度o（n），空间复杂度o（1）

数学规律

假设链表起点到环起点的距离是L，环起点到快慢指针相遇的点的距离是S1，相遇点继续走到环起点的距离是S2。

根据题意，快指针走过的距离是慢指针的两倍，即2S1 = S2。

我们让快指针从链表头开始，慢指针从相遇点开始，每次都走一步，它们一定会在环起点相遇，因为它们走的距离相等，都是L + S1。

因此，当快指针和慢指针相遇时，我们将快指针重新指向链表头，然后让快指针和慢指针一起走，每次都走一步，它们会在环起点相遇。这段代码的作用就是实现这个过程，直到快指针和慢指针相遇为止。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead==nullptr) {
            return nullptr;
        }
        ListNode* slow=pHead, *fast=pHead;
        while (fast!=nullptr&&fast->next!=nullptr) {
            fast=fast->next->next;
            slow=slow->next;
            if (slow==fast) {
                break;
            }
        }    //寻找相遇节点
        if (fast==nullptr||fast->next==nullptr) {
            return nullptr;
        }    //通过快指针检测是否有环
        fast=pHead;
        while (fast!=slow) {
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};