环形链表
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置，索引从 0 开始。
注意：
pos不作为参数进行传递。pos仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true。
否则，返回 false。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 10^4] -10^5 <= Node.val <= 10^5pos为-1或者链表中的一个有效索引
进阶：
你能用 O(1) 内存解决此问题吗？
解法一（哈希集合）：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> visited;
ListNode* cur = head;
while (cur != nullptr)
{
if (visited.count(cur))
{
return true;
}
visited.insert(cur);
cur = cur->next;
}
return false;
}
};
解法二（快慢指针）：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
return true;
}
}
return false;
}
};
核心思想
这题要判断链表中是否存在环。
如果链表没有环，那么从 head 开始不断走 next，最终一定会走到 nullptr。
如果链表有环，那么从某个节点开始会进入一个循环，后面会一直在环里转，永远走不到 nullptr。
最直观的做法是：
- 遍历链表
- 把访问过的节点都放进哈希集合
- 如果再次遇到已经访问过的节点，说明有环
这个方法很好理解，但需要额外空间。
进阶要求 O(1) 内存，所以更推荐快慢指针。
这题最关键的观察是：
如果链表中有环，一个快指针和一个慢指针在环中不断前进，快指针一定会追上慢指针。
解法一：哈希集合
哈希集合中存的是节点指针：
unordered_set<ListNode*> visited;
注意不是存节点值。
因为链表中不同节点的值可能相同，但它们并不是同一个节点。
遍历时，如果当前节点已经在集合中出现过：
visited.count(cur)
说明通过 next 指针再次到达了同一个节点，因此链表有环。
如果一直走到：
cur == nullptr
说明链表正常结束，没有环。
解法二：快慢指针
使用两个指针：
slow：慢指针，每次走一步fast：快指针，每次走两步
如果链表没有环，fast 会先走到链表末尾。
也就是出现：
fast == nullptr
或者：
fast->next == nullptr
这时可以确定链表没有环。
如果链表有环，slow 和 fast 都会进入环。
进入环之后，fast 每次比 slow 多走一步。
它们之间的距离会不断缩小，最终一定会在某个节点相遇。
一旦出现：
slow == fast
说明链表中存在环，返回 true。
为什么快指针一定能追上慢指针
当两个指针都进入环以后，问题就变成了在一个环形跑道上追赶。
每一轮循环：
slow走1步fast走2步
所以相对于 slow，fast 每轮多走 1 步。
如果环的长度是 c，那么两个指针在环上的距离只可能是：
0, 1, 2, ..., c - 1
每轮距离都会变化 1。
最多经过 c 轮，距离一定会变成 0。
距离为 0 时，就表示：
slow == fast
因此只要存在环，快慢指针一定会相遇。
为什么不会误判
快慢指针判断的是两个指针是否指向同一个节点：
slow == fast
不是判断节点值是否相等。
所以即使链表中有多个值相同的节点，也不会误判为有环。
另外，如果链表没有环，fast 会沿着链表向后走，并最终到达 nullptr。
此时循环结束并返回 false，不会无限循环。
边界情况
如果链表为空：
head == nullptr
没有任何节点，不可能有环。
快慢指针解法中，fast == nullptr，循环不会执行，直接返回 false。
如果链表只有一个节点，并且没有自环：
head = [1], pos = -1
此时 fast->next == nullptr，循环也不会执行，返回 false。
如果链表只有一个节点，并且尾部连接自己：
head = [1], pos = 0
那么第一次循环后：
slow仍然指向这个节点fast也仍然指向这个节点
于是 slow == fast，返回 true。
正确性证明
我们证明：快慢指针算法返回的结果满足题意。
结论 1：如果算法返回 true，链表中一定存在环
算法只有在下面条件成立时返回 true：
slow == fast
并且这个判断发生在两个指针至少移动一次之后。
如果链表没有环，从头节点沿着 next 指针向后走是一条单向路径，不可能在不同步长移动后再次到达同一个节点。
两个指针只有在存在环时，才可能在移动后重新指向同一个节点。
所以算法返回 true 时，链表一定有环。
结论 2：如果链表中存在环，算法一定返回 true
如果链表中存在环，slow 和 fast 从 head 出发后，最终都会进入环。
进入环以后，fast 每轮比 slow 多走 1 步。
设环长为 c。
两个指针在环上的相对距离每轮都会减少或增加 1，并且距离只在 0 到 c - 1 之间循环变化。
因此最多经过 c 轮，相对距离一定会变成 0。
也就是：
slow == fast
此时算法返回 true。
结论 3：如果链表中不存在环，算法一定返回 false
如果链表没有环，从 head 出发沿着 next 指针向后走，最终一定会到达 nullptr。
fast 每次走两步，所以它会先到达链表末尾。
当出现：
fast == nullptr || fast->next == nullptr
循环结束，算法返回 false。
因此链表无环时，算法不会错误返回 true，也不会无限循环。
得出结论
由结论 1 可知，算法返回 true 时链表一定有环。
由结论 2 可知，链表有环时算法一定返回 true。
由结论 3 可知，链表无环时算法一定返回 false。
因此快慢指针算法正确。
举例理解
以：
head = [3,2,0,-4], pos = 1
为例。
链表结构是：
3 -> 2 -> 0 -> -4
^ |
|_________|
slow 每次走一步，fast 每次走两步。
当两个指针都进入环以后，fast 会不断追赶 slow。
最终它们会在环中的某个节点相遇，因此返回 true。
再看：
head = [1], pos = -1
链表只有一个节点，并且没有环。
fast->next == nullptr，循环不会执行，直接返回 false。
复杂度分析
解法一
每个节点最多访问一次，哈希集合最多存储所有节点。
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
解法二
快慢指针最多在线性步数内走到末尾或在环中相遇。
只使用两个指针变量。
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
解法二满足进阶要求，是更推荐的做法。