LeetCode 141. 环形链表
题目核心
给定一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达该节点，则链表中存在环。参数 pos 表示链表尾连接到链表中的位置（从 0 开始），仅用于标识，不会作为参数传递。
返回 true 表示有环，false 表示无环。
例 1：1 -> 2 -> 3 -> 4，尾连到 2（pos=1）
返回 true
例 2：1 -> 2，尾连到 0（pos=0）
返回 true
例 3：1 -> 2 -> 3 -> null
返回 false解题思考过程
第一步：理解问题
判断链表是否有环，就是看沿着 next 往下走，会不会永远走不到 null，而是绕回到之前走过的节点。
第二步：哈希表法（直观但费空间）
最直接的想法：遍历链表，把访问过的节点存进 Set，每次访问新节点先查 Set：
- 如果新节点已在 Set 里 → 有环。
- 如果走到
null→ 无环。
时间复杂度：O(n)
空间复杂度：O(n) - 需要存所有节点这个方法简单，但要 O(n) 额外空间。能不能做到 O(1) 空间？
第三步：想到快慢指针
想象两个人在跑道上跑步，一个人快、一个人慢。如果跑道是直的（无环），快的人一定先到终点。如果跑道是环形的，快的人一定会从后面追上慢的人（套圈）。
把这个想法用到链表上：
- 慢指针每次走 1 步。
- 快指针每次走 2 步。
- 如果有环，快指针一定会追上慢指针（相遇）。
- 如果无环，快指针会先走到
null。
这样只需要两个指针，空间 O(1)。
第四步：为什么快慢指针一定能相遇
假设入环时快慢指针距离差为 d：
- 每走一轮，快指针比慢指针多走 1 步，距离差减少 1。
d轮后距离差变成 0，即相遇。
关键在于：快指针最多比慢指针多走一圈，不会"跳过"慢指针。因为每轮距离差只减少 1，不会跳过 0。
所以只要有环，必定相遇。
当前解法：快慢指针
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
// 设置快慢指针,如果两个指针相遇且不为null，则说明有环
let q = head;
let s = head;
while (q != null && q.next != null) {
q = q.next.next;
s = s.next;
if (s === q) {
return true;
}
}
return false;
};代码逐行解释
初始化快慢指针
let q = head;
let s = head;q：快指针（quick），每次走 2 步。s：慢指针（slow），每次走 1 步。- 两个都从头节点出发。
循环条件
while (q != null && q.next != null) {快指针每次走 2 步（q.next.next），所以要保证 q 和 q.next 都不为 null，否则会报错。
- 如果
q走到null，或q.next是null，说明到链表末尾了，无环。
移动指针
q = q.next.next;
s = s.next;- 快指针走 2 步。
- 慢指针走 1 步。
判断相遇
if (s === q) {
return true;
}如果快慢指针指向同一个节点（注意是引用相等 ===，不是值相等），说明快指针追上了慢指针，链表有环，返回 true。
无环情况
return false;如果循环正常结束（快指针走到末尾），说明没有环，返回 false。
执行过程示例
有环的情况
链表：1 -> 2 -> 3 -> 4 -> 2（4 的 next 指向 2，形成环）
初始：s=1, q=1
第 1 轮：s=2, q=3
第 2 轮：s=3, q=2（快指针绕了一圈）
第 3 轮：s=4, q=4 → s === q，相遇！返回 true无环的情况
链表：1 -> 2 -> 3 -> null
初始：s=1, q=1
第 1 轮：q=3, s=2
第 2 轮：q.next.next = null，q.next = null
循环条件 q.next != null 不满足，退出循环
返回 false为什么初始时 s 和 q 都指向 head 不会误判
初始时 s === q（都是 head），但相遇判断在移动之后才执行，所以不会在初始状态就误判为有环。
如果担心，也可以让快慢指针从不同位置出发，但这道题当前写法是正确的。
复杂度分析
- 时间复杂度：
O(n)。慢指针最多走 n 步，快指针最多走 2n 步，相遇前总共最多走约 n 步。 - 空间复杂度：
O(1)。只用了两个指针变量。
两种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 哈希表法 | O(n) | O(n) | 直观易懂，但需要额外空间 |
| 快慢指针 | O(n) | O(1) | 空间最优，面试首选 |
快慢指针是这道题的最优解，既省空间又简洁。这个思路也是下一题 142. 环形链表 II 找环入口的基础。