题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则说明链表中存在环。
如果链表中存在环，返回 true ；否则，返回 false 。
题目分析
这道题是一道经典的链表题。
题目的目标很明确：判断链表里是否存在环。
null，就说明没有环。
这种方法当然可以做，但需要额外空间。
而这道题更经典的做法，是使用 快慢指针。
也叫做 Floyd 判圈算法。
核心思路：快慢指针
我们定义两个指针：
-
slow：每次走一步 -
fast：每次走两步
然后让它们同时从链表头节点出发。
情况一：链表没有环
如果没有环，那么 fast 一定会先走到链表末尾。
也就是说，会出现：
-
fast == null -
或者
fast.next == null
这时就可以直接返回 false。
情况二：链表有环
如果有环，那么 fast 和 slow 都会进入这个环。
由于 fast 每次比 slow 多走一步，所以它们之间的距离会不断变化。
可以把这理解成在环形跑道上跑步：
-
慢指针每次走 1 步
-
快指针每次走 2 步
只要两个人一直在环里跑，快的人迟早会从后面追上慢的人。
所以如果链表有环，fast 和 slow 一定会在某个时刻相遇。
一旦相遇，就可以直接返回 true。
代码实现
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
代码讲解
1. 初始化快慢指针
ListNode slow = head;
ListNode fast = head;
一开始，两个指针都指向头节点。
-
slow用来慢速前进 -
fast用来快速前进
2. 循环条件
while (fast != null && fast.next != null)
这里非常关键。
因为快指针一次要走两步，也就是：
fast = fast.next.next;
所以我们必须先保证：
-
fast不为空 -
fast.next也不为空
否则就会出现空指针异常。
如果循环条件不满足，就说明链表已经走到尽头了，也就说明没有环。
3. 快慢指针移动
slow = slow.next;
fast = fast.next.next;
-
慢指针每次走一步
-
快指针每次走两步
这就是整个算法的核心。
4. 判断是否相遇
if (fast == slow) {
return true;
}
如果两个指针指向了同一个节点，说明它们在环中相遇了。
既然能相遇，就说明链表中一定存在环。
所以直接返回 true。
举个例子
假设链表如下：
3 -> 2 -> 0 -> -4
^ |
|_________|
这里 -4 的 next 指向值为 2 的节点，所以链表中有环。
运行过程：
初始状态
-
slow = 3 -
fast = 3
第一次循环后
-
slow = 2 -
fast = 0
第二次循环后
-
slow = 0 -
fast = 2
第三次循环后
-
slow = -4 -
fast = -4
此时二者相遇，返回 true。
为什么快慢指针一定会相遇？
这个问题是这道题最重要的地方。
假设环的长度是 k。
当 slow 进入环后，fast 也一定会进入环。
进入环之后：
-
slow每次前进 1 格 -
fast每次前进 2 格
所以 fast 相对于 slow，每次都会多走 1 格。
那么它们之间的距离会每轮缩短 1（模 k 意义下）。
因为环的长度是有限的，所以最多经过 k 轮，fast 一定会追上 slow。
这就是为什么只要有环，它们一定会相遇。
复杂度分析
时间复杂度
O(n)
虽然看起来是两个指针在移动，但每个节点最多被访问有限次，所以整体时间复杂度仍然是线性的。
空间复杂度
O(1)
整个过程中只使用了两个额外指针，没有使用额外的数据结构。
和哈希表做法对比
这道题其实还有一种比较直观的做法：
-
用
HashSet存每一个访问过的节点 -
如果某个节点已经在集合中出现过，就说明有环
这种方法的优点是容易理解。
但缺点也很明显：
-
需要额外的
O(n)空间
而快慢指针法只需要 O(1) 空间，所以更优，也更经典。
总结
这道题是链表中的经典题目，重点并不在代码有多复杂，而在于理解 快慢指针判环 的思想。
我们可以记住下面这个结论：
-
没有环：快指针会先走到
null -
有环：快指针最终一定会追上慢指针
所以这道题最优解就是：
-
定义快慢指针
-
快指针每次走两步，慢指针每次走一步
-
如果相遇，说明有环
-
如果快指针走到末尾，说明无环
这类思路在后面的链表题中也会经常出现，比如：
-
环形链表 II
-
找链表中点
-
判断链表是否为回文链表
