题目
给定一个链表的头节点 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
解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
解答
- 使用hashset存储链表元素的地址，当使用快慢指针确定环形链表存在时，返回相应的环形节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr) // 如果链表为空或者只有一个元素，则返回null
return nullptr;
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) return nullptr;
fast = fast->next->next;
slow = slow->next;
}
//此时已经发现有环了，使用hashset存储链表元素地址，若有相同地址的元素就返回该元素
unordered_set<ListNode*> nodes;
ListNode* cur = head;
while (cur != nullptr) {
if (nodes.count(cur)) {
return cur;
}
else {
nodes.insert(cur);
cur = cur->next;
}
}
return nullptr;
}
};- 快慢指针法
利用快慢指针，找到链表中是否存在环。若存在环，则将快指针重新指向链表的头结点，并将快慢指针以相同的速度向前移动，直到两个指针相遇，即为环的入口节点。
假设链表的长度为L，环的长度为C，环的入口节点距离头节点的距离为A，快慢指针相遇的节点距离环的入口节点的距离为B。
当快慢指针相遇时，快指针走过的距离是慢指针的两倍，即：$2 \times (A + B) = A + B + n \times C$其中n是快指针在环中走过的圈数。化简得：$A = (n - 1) \times C + (C - B)$。这个式子的意义是，从头节点到环的入口节点的距离等于从相遇点到环的入口节点的距离加上(n - 1)圈的环的长度。
因此，如果让一个新的指针cur从头节点开始走，同时让slow从相遇点开始走，每次都走一步，那么它们会在环的入口节点相遇，因为它们走过的距离都是A。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 判断链表是否为空或只有一个元素
if (head == NULL || head->next == NULL) {
return NULL;
}
// 定义快慢指针，初始值指向头结点
ListNode* fast = head;
ListNode* slow = head;
// 判断是否存在环
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next; // 快指针走两步
slow = slow->next; // 慢指针走一步
if (fast == slow) { // 快慢指针相遇
ListNode* start = head; // 从头结点开始，与慢指针同时前进，相遇点即为环的起点
while (start != slow) {
start = start->next;
slow = slow->next;
}
return start;
}
}
return NULL; // 遍历完链表，仍未找到环，返回NULL
}
};
注：在 while 循环中，因为 fast 比 slow 快，所以应该先判断 fast 是否为 NULL 或 fast->next 是否为 NULL，以保证程序的正确性。