题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
分析
哈希表法
遍历链表中的每个节点并记录下来。一旦遇到了此前遍历过的节点，就可以判定链表中存在环，直接返回该节点。
时间复杂度：O()，
为链表中节点的数目
空间复杂度：O()
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 使用哈希集合来存储已经访问过的节点
std::unordered_set<ListNode*> visited;
// 遍历链表
while (head != nullptr) {
// 检查当前节点是否已经在哈希集合中
if (visited.count(head)) {
// 如果存在，说明找到了环的入口节点，返回该节点
return head;
}
// 将当前节点插入到哈希集合中
visited.insert(head);
// 移动到下一个节点
head = head->next;
}
// 如果遍历完整个链表都没有找到环，返回 nullptr
return nullptr;
}
};快慢指针法
判断是否有环：首先使用快慢指针判断链表中是否存在环。slow 指针每次移动一步，fast 指针每次移动两步，如果它们相遇，则说明链表中存在环。
寻找环的入口：当快慢指针相遇后，将 slow 指针重新指向链表头节点，然后 slow 和 fast 指针以相同的速度（每次移动一步）继续移动，它们再次相遇的节点就是环的入口节点。
数学推导
设链表的头节点为
head，链表中环的入口节点为entry，从链表头到环入口的节点数为a，从环入口到快慢指针相遇点的节点数为b，从快慢指针相遇点再到环入口的节点数为c，则环的长度为b + c慢指针
slow每次移动一步，快指针fast每次移动两步。当快慢指针相遇时，假设慢指针移动了 a + b 步，快指针移动了y步。因为快指针速度是慢指针的两倍，所以y = 2(a+b)又因为快指针比慢指针多走了若干圈环，设快指针在环里走了
n圈（n为正整数），则有y = a + n(b + c) + b。将y = 2(a+b)代入y = a + n(b + c) + b可得：a = c + (n - 1)(b + c)于是从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。即当
slow和fast再次相遇时，相遇的节点就是环的入口节点
时间复杂度：O()，
为链表中节点的数目
空间复杂度：O(1)
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 如果链表为空或者只有一个节点，肯定不存在环，返回 nullptr
if (head == nullptr || head->next == nullptr) {
return nullptr;
}
// 定义快慢指针
ListNode* slow = head;
ListNode* fast = head;
// 标记是否有环
bool hasCycle = false;
// 移动快慢指针，快指针每次移动两步，慢指针每次移动一步
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
// 如果快慢指针相遇，说明存在环
if (slow == fast) {
hasCycle = true;
break;
}
}
// 如果没有环，返回 nullptr
if (!hasCycle) {
return nullptr;
}
// 让慢指针回到头节点
slow = head;
// 快慢指针以相同速度移动，再次相遇的节点就是环的入口节点
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};