AlgoViz Lab交互式算法学习Algorithms first
环形链表 · 交互式算法学习
判断链表是否存在环。
#141 · 链表
环形链表
Linked List Cycle
head = [3,2,0,-4], tail.next → index 1链表8 个关键状态
步骤 1slow 与 fast 都从头节点开始。
slow=0, fast=0推荐
快慢指针
时间
O(n)空间 O(1)慢指针一步、快指针两步；有环时必在环内相遇。
1function hasCycle(head) {2 let slow = head,3 fast = head;4 while (fast && fast.next) {5 slow = slow.next;6 fast = fast.next.next;7 if (slow === fast) return true;8 }9 return false;10}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/**2 * Definition for singly-linked list.3 * class ListNode {4 * int val;5 * ListNode next;6 * ListNode(int x) {7 * val = x;8 * next = null;9 * }10 * }11 */12public class Solution {13 public boolean hasCycle(ListNode head) {14 Set<ListNode> s = new HashSet<>();15 for (; head != null; head = head.next) {16 if (!s.add(head)) {17 return true;18 }19 }20 return false;21 }22}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
环形链表 · 解法对比
判断链表是否存在环。
- 测试用例
head = [3,2,0,-4], tail.next → index 1- 题目分类
- 链表
- 解法对比
- 2
访问节点集合
把访问过的节点放进集合，再次遇到即有环。
- 时间
O(n)- 空间
O(n)
快慢指针
慢指针一步、快指针两步；有环时必在环内相遇。
- 时间
O(n)- 空间
O(1)
为什么有效
若存在环，快指针每轮比慢指针多走一步，进入环后两者的相对距离会不断缩小并最终相遇。
关键不变量
每轮结束时 slow 前进一条 next 边，fast 前进两条；只要 fast 能继续走，所有访问都合法。
易错点
- 循环前要同时检查 fast 和 fast.next。
- 不能通过节点值判断相遇，必须比较节点引用。
边界情况
- 空链表和单个无环节点返回 false。
- 单节点自环返回 true。
- 环入口可能就是头节点。
更多案例
[3,2,0,-4], tail→index 1true快慢指针在环内相遇。
[1,2], tail→index 0true整个链表构成环。
[1], tail→nullfalsefast 无法继续走两步。