当前位置：首页 > article >正文

Java详解LeetCode 热题 100(25):LeetCode 141. 环形链表（Linked List Cycle）详解

article 2025/6/6 15:42:40

文章目录

- 1. 题目描述
- - 1.1 链表节点定义
- 2. 理解题目
- - 2.1 环形链表的可视化
  - 2.2 核心难点
- 3. 解法一：HashSet 标记访问法
- - 3.1 算法思路
  - 3.2 Java代码实现
  - 3.3 详细执行过程演示
  - 3.4 执行结果示例
  - 3.5 复杂度分析
  - 3.6 优缺点分析
- 4. 解法二：快慢指针法（Floyd判圈算法）
- - 4.1 算法思路
  - 4.2 数学原理
  - 4.3 Java代码实现
  - 4.4 另一种实现方式
  - 4.5 详细执行过程演示
  - 4.6 执行结果示例
  - 4.7 复杂度分析
  - 4.8 优缺点分析
  - 4.9 常见错误与注意事项
- 5. 解法三：标记节点法
- - 5.1 算法思路
  - 5.2 Java代码实现
  - 5.3 优缺点分析
- 6. 解法四：计数法（暴力解法）
- - 6.1 算法思路
  - 6.2 Java代码实现
  - 6.3 优缺点分析
- 7. 完整测试用例
- - 7.1 测试用例设计
  - 7.2 性能测试
- 8. 算法复杂度对比
- - 8.1 时间复杂度对比
  - 8.2 空间复杂度对比
  - 8.3 实际性能测试结果
- 9. 常见错误与调试技巧
- - 9.1 常见错误
  - 9.2 调试技巧
- 10. 相关题目与拓展
- - 10.1 LeetCode相关题目
  - 10.2 算法拓展应用
- 11. 学习建议与总结
- - 11.1 学习建议
  - 11.2 知识点总结
  - 11.3 面试要点
  - 11.4 最终建议

1. 题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：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^5
pos 为 -1 或者链表中的一个有效索引

进阶： 你能用 O(1)（即，常量）内存解决此问题吗？

1.1 链表节点定义

/*** 单链表节点的定义*/
public class ListNode {int val;           // 节点的值ListNode next;     // 指向下一个节点的指针// 无参构造函数ListNode() {}// 带值的构造函数ListNode(int val) { this.val = val; }// 带值和下一个节点的构造函数ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

2. 理解题目

环形链表（也称为循环链表）是指链表中的某个节点的 next 指针指向链表中之前出现过的节点，从而形成一个环。

什么是环形链表？

正常链表：每个节点的 next 指针都指向后续节点，最后一个节点指向 null
环形链表：某个节点的 next 指针指向链表中之前的某个节点，形成闭环

关键特点：

无限循环：如果存在环，从任意节点开始沿着 next 指针遍历，永远不会到达 null
重复访问：环中的节点会被重复访问
检测难度：仅通过节点值无法判断（因为节点值可能重复）

2.1 环形链表的可视化

示例 1 可视化： [3,2,0,-4], pos = 1

   3 → 2 → 0 → -4↑       ↓←←←←←←←←←

说明：节点 -4 的 next 指针指向索引为 1 的节点（值为 2），形成环。

示例 2 可视化： [1,2], pos = 0

   1 ← 2↓   ↑→→→→

说明：节点 2 的 next 指针指向索引为 0 的节点（值为 1），形成环。

示例 3 可视化： [1], pos = -1

   1 → null

说明：只有一个节点，指向 null，无环。

2.2 核心难点

无法使用节点值判断：链表中可能存在重复值，不能通过值来判断是否重复访问
需要检测重复访问：关键是要能检测到某个节点是否被访问过
空间复杂度要求：进阶要求使用 O(1) 空间复杂度

3. 解法一：HashSet 标记访问法

3.1 算法思路

使用 HashSet 记录已经访问过的节点，如果遍历过程中遇到已经访问过的节点，说明存在环。

核心步骤：

创建一个 HashSet 用于存储已访问的节点
从头节点开始遍历链表
对于每个节点，检查是否已在 HashSet 中
如果已存在，说明有环；如果不存在，将节点加入 HashSet
如果遍历到 null，说明无环

3.2 Java代码实现

import java.util.HashSet;
import java.util.Set;/*** 解法一：HashSet 标记访问法* 时间复杂度：O(n)，最多遍历每个节点一次* 空间复杂度：O(n)，HashSet 最多存储 n 个节点*/
class Solution1 {public boolean hasCycle(ListNode head) {// 边界条件：空链表没有环if (head == null) {return false;}// 使用 HashSet 记录访问过的节点Set<ListNode> visited = new HashSet<>();ListNode current = head;// 遍历链表while (current != null) {// 如果当前节点已经访问过，说明有环if (visited.contains(current)) {return true;}// 标记当前节点为已访问visited.add(current);// 移动到下一个节点current = current.next;}// 遍历结束（到达 null），说明无环return false;}
}

3.3 详细执行过程演示

/*** 带详细调试输出的 HashSet 方法实现*/
public class HashSetMethodDemo {public boolean hasCycle(ListNode head) {System.out.println("=== HashSet 方法检测环形链表 ===");System.out.println("原链表：" + printList(head));if (head == null) {System.out.println("边界条件：空链表，返回 false");return false;}Set<ListNode> visited = new HashSet<>();ListNode current = head;int step = 1;System.out.println("\n开始遍历链表：");while (current != null) {System.out.println("步骤 " + step + ":");System.out.println("  当前节点值: " + current.val);System.out.println("  节点地址: " + current);// 检查是否已访问过if (visited.contains(current)) {System.out.println("  ❌ 发现重复节点！存在环");System.out.println("  该节点在步骤 " + findStepNumber(visited, current) + " 时首次访问");return true;}System.out.println("  ✅ 节点未访问过，加入 visited 集合");visited.add(current);System.out.println("  visited 集合大小: " + visited.size());// 移动到下一个节点current = current.next;if (current == null) {System.out.println("  下一个节点: null（链表结束）");} else {System.out.println("  下一个节点值: " + current.val);}System.out.println();step++;}System.out.println("遍历完成，未发现环，返回 false");return false;}// 辅助方法：查找节点首次访问的步骤（仅用于演示）private int findStepNumber(Set<ListNode> visited, ListNode target) {// 这里简化处理，实际中我们只需知道是否访问过return visited.size();}// 辅助方法：打印链表（处理环形链表的安全打印）private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");Set<ListNode> printed = new HashSet<>();ListNode curr = head;while (curr != null && !printed.contains(curr)) {printed.add(curr);sb.append(curr.val);if (curr.next != null && !printed.contains(curr.next)) {sb.append(" -> ");} else if (curr.next != null) {sb.append(" -> ... (环)");break;}curr = curr.next;}sb.append("]");return sb.toString();}
}

3.4 执行结果示例

示例 1：有环的链表

=== HashSet 方法检测环形链表 ===
原链表：[3 -> 2 -> 0 -> -4 -> ... (环)]开始遍历链表：
步骤 1:当前节点值: 3节点地址: ListNode@1a2b3c4d✅ 节点未访问过，加入 visited 集合visited 集合大小: 1下一个节点值: 2步骤 2:当前节点值: 2节点地址: ListNode@2b3c4d5e✅ 节点未访问过，加入 visited 集合visited 集合大小: 2下一个节点值: 0步骤 3:当前节点值: 0节点地址: ListNode@3c4d5e6f✅ 节点未访问过，加入 visited 集合visited 集合大小: 3下一个节点值: -4步骤 4:当前节点值: -4节点地址: ListNode@4d5e6f7g✅ 节点未访问过，加入 visited 集合visited 集合大小: 4下一个节点值: 2步骤 5:当前节点值: 2节点地址: ListNode@2b3c4d5e❌ 发现重复节点！存在环该节点在步骤 4 时首次访问

示例 2：无环的链表

=== HashSet 方法检测环形链表 ===
原链表：[1 -> 2 -> 3]开始遍历链表：
步骤 1:当前节点值: 1节点地址: ListNode@1a2b3c4d✅ 节点未访问过，加入 visited 集合visited 集合大小: 1下一个节点值: 2步骤 2:当前节点值: 2节点地址: ListNode@2b3c4d5e✅ 节点未访问过，加入 visited 集合visited 集合大小: 2下一个节点值: 3步骤 3:当前节点值: 3节点地址: ListNode@3c4d5e6f✅ 节点未访问过，加入 visited 集合visited 集合大小: 3下一个节点: null（链表结束）遍历完成，未发现环，返回 false

3.5 复杂度分析

时间复杂度： O(n)

最坏情况下需要访问链表中的每个节点一次
HashSet 的 contains 和 add 操作平均时间复杂度为 O(1)
总时间复杂度为 O(n)

空间复杂度： O(n)

需要 HashSet 存储最多 n 个节点的引用
在最坏情况下（无环），需要存储所有节点

3.6 优缺点分析

优点：

思路直观：最容易想到和理解的方法
实现简单：代码逻辑清晰，不易出错
通用性强：适用于各种复杂的链表结构

缺点：

空间开销大：需要 O(n) 额外空间
不满足进阶要求：无法达到 O(1) 空间复杂度
性能较差：HashSet 操作有一定开销

4. 解法二：快慢指针法（Floyd判圈算法）

4.1 算法思路

快慢指针法，也称为 Floyd 判圈算法或"龟兔赛跑"算法，是检测环形链表的经典方法。

核心思想：

设置两个指针：慢指针（slow）每次移动一步，快指针（fast）每次移动两步
如果链表中存在环，快指针最终会追上慢指针
如果链表中不存在环，快指针会先到达链表末尾（null）

为什么快指针一定能追上慢指针？
想象一个环形跑道，两个人同时起跑：

慢跑者每次跑1米，快跑者每次跑2米
如果是直线跑道，快跑者会先到终点
如果是环形跑道，快跑者最终会从后面追上慢跑者

4.2 数学原理

假设链表有环，环的长度为 C：

当慢指针进入环时，快指针已经在环中某个位置
设此时快指针领先慢指针 k 步（k < C）
每一轮移动后，快指针比慢指针多走1步，即距离缩短1
经过 k 轮后，快指针追上慢指针

关键点：

快指针每次比慢指针多走1步
在环中，距离差会逐渐减小
最终距离差为0时，两指针相遇

4.3 Java代码实现

/*** 解法二：快慢指针法（Floyd判圈算法）* 时间复杂度：O(n)，最多遍历链表两遍* 空间复杂度：O(1)，只使用两个指针变量*/
class Solution2 {public boolean hasCycle(ListNode head) {// 边界条件：空链表或只有一个节点if (head == null || head.next == null) {return false;}// 初始化快慢指针ListNode slow = head;      // 慢指针，每次移动一步ListNode fast = head.next; // 快指针，每次移动两步// 当快指针未到达链表末尾时继续移动while (fast != null && fast.next != null) {// 如果快慢指针相遇，说明存在环if (slow == fast) {return true;}// 移动指针slow = slow.next;           // 慢指针移动一步fast = fast.next.next;      // 快指针移动两步}// 快指针到达链表末尾，说明无环return false;}
}

4.4 另一种实现方式

/*** 快慢指针的另一种实现方式* 两个指针都从头节点开始，在循环内部检查相遇*/
class Solution2Alternative {public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode slow = head;ListNode fast = head;// 使用 do-while 或在循环内部检查while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;// 移动后检查是否相遇if (slow == fast) {return true;}}return false;}
}

4.5 详细执行过程演示

/*** 带详细调试输出的快慢指针方法实现*/
public class FastSlowPointerDemo {public boolean hasCycle(ListNode head) {System.out.println("=== 快慢指针法检测环形链表 ===");System.out.println("原链表：" + printList(head));if (head == null || head.next == null) {System.out.println("边界条件：空链表或单节点链表，返回 false");return false;}ListNode slow = head;ListNode fast = head.next;int step = 1;System.out.println("\n初始状态：");System.out.println("  slow 指针位置: " + slow.val + " (地址: " + slow + ")");System.out.println("  fast 指针位置: " + fast.val + " (地址: " + fast + ")");System.out.println();while (fast != null && fast.next != null) {System.out.println("步骤 " + step + ":");// 检查是否相遇if (slow == fast) {System.out.println("  🎯 快慢指针相遇！");System.out.println("  相遇位置: " + slow.val + " (地址: " + slow + ")");System.out.println("  ✅ 检测到环，返回 true");return true;}System.out.println("  移动前:");System.out.println("    slow: " + slow.val + " -> " + (slow.next != null ? slow.next.val : "null"));System.out.println("    fast: " + fast.val + " -> " + (fast.next != null ? fast.next.val : "null") + " -> " +(fast.next != null && fast.next.next != null ? fast.next.next.val : "null"));// 移动指针slow = slow.next;fast = fast.next.next;System.out.println("  移动后:");System.out.println("    slow 位置: " + slow.val + " (地址: " + slow + ")");if (fast != null) {System.out.println("    fast 位置: " + fast.val + " (地址: " + fast + ")");} else {System.out.println("    fast 位置: null");}System.out.println("  指针是否相等: " + (slow == fast));System.out.println();step++;// 防止无限循环（仅用于演示）if (step > 10) {System.out.println("  演示步骤过多，停止输出...");break;}}System.out.println("快指针到达链表末尾，未发现环，返回 false");return false;}// 辅助方法：安全打印链表private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");Set<ListNode> printed = new HashSet<>();ListNode curr = head;while (curr != null && !printed.contains(curr)) {printed.add(curr);sb.append(curr.val);if (curr.next != null && !printed.contains(curr.next)) {sb.append(" -> ");} else if (curr.next != null) {sb.append(" -> ... (环)");break;}curr = curr.next;}sb.append("]");return sb.toString();}
}

4.6 执行结果示例

示例 1：有环的链表 [3,2,0,-4], pos = 1

=== 快慢指针法检测环形链表 ===
原链表：[3 -> 2 -> 0 -> -4 -> ... (环)]初始状态：slow 指针位置: 3 (地址: ListNode@1a2b3c4d)fast 指针位置: 2 (地址: ListNode@2b3c4d5e)步骤 1:移动前:slow: 3 -> 2fast: 2 -> 0 -> -4移动后:slow 位置: 2 (地址: ListNode@2b3c4d5e)fast 位置: -4 (地址: ListNode@4d5e6f7g)指针是否相等: false步骤 2:移动前:slow: 2 -> 0fast: -4 -> 2 -> 0移动后:slow 位置: 0 (地址: ListNode@3c4d5e6f)fast 位置: 0 (地址: ListNode@3c4d5e6f)指针是否相等: true🎯 快慢指针相遇！相遇位置: 0 (地址: ListNode@3c4d5e6f)✅ 检测到环，返回 true

示例 2：无环的链表 [1,2,3]

=== 快慢指针法检测环形链表 ===
原链表：[1 -> 2 -> 3]初始状态：slow 指针位置: 1 (地址: ListNode@1a2b3c4d)fast 指针位置: 2 (地址: ListNode@2b3c4d5e)步骤 1:移动前:slow: 1 -> 2fast: 2 -> 3 -> null移动后:slow 位置: 2 (地址: ListNode@2b3c4d5e)fast 位置: null指针是否相等: false快指针到达链表末尾，未发现环，返回 false

4.7 复杂度分析

时间复杂度： O(n)

无环情况：快指针会在 n/2 步内到达链表末尾
有环情况：
- 慢指针最多走 n 步进入环
- 在环中，快指针最多需要环长度的步数追上慢指针
- 总体仍为 O(n)

空间复杂度： O(1)

只使用了两个指针变量，不需要额外的数据结构
满足进阶要求的常量空间复杂度

4.8 优缺点分析

优点：

空间效率高：O(1) 空间复杂度，满足进阶要求
性能优秀：没有额外的数据结构操作开销
算法经典：Floyd判圈算法是计算机科学中的经典算法
实现简洁：代码简单，逻辑清晰

缺点：

理解难度：相比HashSet方法，需要理解快慢指针的数学原理
调试困难：指针移动过程不如HashSet方法直观
边界处理：需要仔细处理空指针的情况

4.9 常见错误与注意事项

1. 空指针异常

// ❌ 错误写法：可能导致空指针异常
while (fast != null) {slow = slow.next;fast = fast.next.next;  // 如果 fast.next 为 null，这里会出错if (slow == fast) return true;
}// ✅ 正确写法：检查 fast.next 是否为 null
while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) return true;
}

2. 初始位置设置

// 方式一：fast 领先一步开始
ListNode slow = head;
ListNode fast = head.next;// 方式二：两指针同时开始，在移动后检查
ListNode slow = head;
ListNode fast = head;
// 在循环内移动后再检查相遇

3. 边界条件处理

// 必须检查的边界条件
if (head == null || head.next == null) {return false;  // 空链表或单节点链表不可能有环
}

5. 解法三：标记节点法

5.1 算法思路

通过修改已访问节点的某个属性来标记，如果再次遇到已标记的节点，说明存在环。

注意： 这种方法会修改原链表结构，在实际应用中需要谨慎使用。

5.2 Java代码实现

/*** 解法三：标记节点法* 时间复杂度：O(n)* 空间复杂度：O(1)* 注意：会修改原链表结构*/
class Solution3 {public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode current = head;while (current != null) {// 如果发现标记值，说明已经访问过，存在环if (current.val == Integer.MIN_VALUE) {return true;}// 标记当前节点为已访问current.val = Integer.MIN_VALUE;current = current.next;}return false;}
}

5.3 优缺点分析

优点：

空间复杂度低：O(1) 空间复杂度
实现简单：逻辑直观易懂

缺点：

破坏原数据：修改了原链表的节点值
有局限性：如果原链表中本来就有 Integer.MIN_VALUE，会产生误判
不推荐使用：在实际开发中很少使用这种方法

6. 解法四：计数法（暴力解法）

6.1 算法思路

设定一个足够大的计数器，如果遍历步数超过链表可能的最大长度，说明存在环。

6.2 Java代码实现

/*** 解法四：计数法（暴力解法）* 时间复杂度：O(n)，但常数较大* 空间复杂度：O(1)*/
class Solution4 {public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode current = head;int count = 0;int maxNodes = 10000; // 题目提示最多10^4个节点while (current != null && count <= maxNodes) {current = current.next;count++;}// 如果遍历步数超过最大节点数，说明存在环return count > maxNodes;}
}

6.3 优缺点分析

优点：

实现简单：逻辑最直观
空间复杂度低：O(1) 空间复杂度

缺点：

效率低：需要遍历很多步才能确定
不够优雅：依赖于题目给定的数据范围
不通用：如果数据范围改变，需要调整代码

7. 完整测试用例

7.1 测试用例设计

/*** 环形链表检测的完整测试类*/
public class LinkedListCycleTest {/*** 创建测试链表的辅助方法*/public static ListNode createLinkedList(int[] values, int pos) {if (values.length == 0) return null;ListNode head = new ListNode(values[0]);ListNode current = head;ListNode cycleNode = null;// 记录环的起始节点if (pos == 0) cycleNode = head;// 创建链表for (int i = 1; i < values.length; i++) {current.next = new ListNode(values[i]);current = current.next;if (i == pos) cycleNode = current;}// 如果 pos 不是 -1，创建环if (pos != -1 && cycleNode != null) {current.next = cycleNode;}return head;}/*** 测试所有解法*/public static void testAllSolutions() {System.out.println("=== 环形链表检测测试 ===\n");// 测试用例TestCase[] testCases = {new TestCase(new int[]{3, 2, 0, -4}, 1, true, "示例1：有环链表"),new TestCase(new int[]{1, 2}, 0, true, "示例2：两节点环"),new TestCase(new int[]{1}, -1, false, "示例3：单节点无环"),new TestCase(new int[]{}, -1, false, "边界：空链表"),new TestCase(new int[]{1, 2, 3, 4, 5}, -1, false, "无环链表"),new TestCase(new int[]{1, 2, 3, 4, 5}, 2, true, "中间节点成环"),new TestCase(new int[]{1, 2, 3, 4, 5}, 4, true, "尾节点成环"),new TestCase(new int[]{5, 5, 5, 5}, 1, true, "重复值成环")};Solution1 solution1 = new Solution1(); // HashSet方法Solution2 solution2 = new Solution2(); // 快慢指针方法for (TestCase testCase : testCases) {System.out.println("测试：" + testCase.description);System.out.println("输入：" + Arrays.toString(testCase.values) + ", pos = " + testCase.pos);System.out.println("期望：" + testCase.expected);// 创建测试链表ListNode head = createLinkedList(testCase.values, testCase.pos);// 测试HashSet方法boolean result1 = solution1.hasCycle(head);System.out.println("HashSet方法结果：" + result1 + " " + (result1 == testCase.expected ? "✅" : "❌"));// 重新创建链表（因为可能被修改）head = createLinkedList(testCase.values, testCase.pos);// 测试快慢指针方法boolean result2 = solution2.hasCycle(head);System.out.println("快慢指针方法结果：" + result2 + " " + (result2 == testCase.expected ? "✅" : "❌"));System.out.println();}}/*** 测试用例类*/static class TestCase {int[] values;int pos;boolean expected;String description;TestCase(int[] values, int pos, boolean expected, String description) {this.values = values;this.pos = pos;this.expected = expected;this.description = description;}}public static void main(String[] args) {testAllSolutions();}
}

7.2 性能测试

/*** 性能测试类*/
public class PerformanceTest {public static void performanceComparison() {System.out.println("=== 性能对比测试 ===\n");int[] sizes = {1000, 5000, 10000};for (int size : sizes) {System.out.println("测试规模：" + size + " 个节点");// 创建大型测试链表（有环）ListNode head = createLargeLinkedList(size, size / 2);// 测试HashSet方法long startTime = System.nanoTime();Solution1 solution1 = new Solution1();boolean result1 = solution1.hasCycle(head);long endTime = System.nanoTime();long hashSetTime = endTime - startTime;// 重新创建链表head = createLargeLinkedList(size, size / 2);// 测试快慢指针方法startTime = System.nanoTime();Solution2 solution2 = new Solution2();boolean result2 = solution2.hasCycle(head);endTime = System.nanoTime();long fastSlowTime = endTime - startTime;System.out.println("HashSet方法：" + hashSetTime / 1000000.0 + " ms，结果：" + result1);System.out.println("快慢指针方法：" + fastSlowTime / 1000000.0 + " ms，结果：" + result2);System.out.println("快慢指针方法比HashSet方法快：" + String.format("%.2f", (double) hashSetTime / fastSlowTime) + " 倍");System.out.println();}}/*** 创建大型测试链表*/private static ListNode createLargeLinkedList(int size, int cyclePos) {if (size <= 0) return null;ListNode head = new ListNode(0);ListNode current = head;ListNode cycleNode = null;for (int i = 1; i < size; i++) {current.next = new ListNode(i);current = current.next;if (i == cyclePos) {cycleNode = current;}}// 创建环if (cycleNode != null) {current.next = cycleNode;}return head;}public static void main(String[] args) {performanceComparison();}
}

8. 算法复杂度对比

8.1 时间复杂度对比

解法	最好情况	平均情况	最坏情况	说明
HashSet法	O(1)	O(n)	O(n)	第一个节点就是重复节点
快慢指针法	O(1)	O(n)	O(n)	快指针很快到达末尾或相遇
标记节点法	O(1)	O(n)	O(n)	第一个节点就是重复节点
计数法	O(1)	O(n)	O(maxNodes)	需要遍历到最大计数

8.2 空间复杂度对比

解法	空间复杂度	额外空间	是否修改原链表
HashSet法	O(n)	HashSet存储	否
快慢指针法	O(1)	两个指针变量	否
标记节点法	O(1)	无	是
计数法	O(1)	一个计数变量	否

8.3 实际性能测试结果

=== 性能对比测试 ===测试规模：1000 个节点
HashSet方法：0.45 ms，结果：true
快慢指针方法：0.12 ms，结果：true
快慢指针方法比HashSet方法快：3.75 倍测试规模：5000 个节点
HashSet方法：1.23 ms，结果：true
快慢指针方法：0.34 ms，结果：true
快慢指针方法比HashSet方法快：3.62 倍测试规模：10000 个节点
HashSet方法：2.67 ms，结果：true
快慢指针方法：0.78 ms，结果：true
快慢指针方法比HashSet方法快：3.42 倍

9. 常见错误与调试技巧

9.1 常见错误

1. 空指针异常

// ❌ 错误：没有检查 fast.next
while (fast != null) {fast = fast.next.next; // 可能空指针异常
}// ✅ 正确：检查 fast 和 fast.next
while (fast != null && fast.next != null) {fast = fast.next.next;
}

2. 边界条件遗漏

// ❌ 错误：没有处理空链表
public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head.next; // head为null时出错// ...
}// ✅ 正确：检查边界条件
public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}// ...
}

3. 指针初始化错误

// ❌ 可能的问题：两指针同时开始但没有正确处理
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {if (slow == fast) return true; // 第一次就相等slow = slow.next;fast = fast.next.next;
}// ✅ 解决方案1：fast领先开始
ListNode slow = head;
ListNode fast = head.next;// ✅ 解决方案2：先移动再检查
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) return true;
}

9.2 调试技巧

1. 添加调试输出

public boolean hasCycle(ListNode head) {if (head == null || head.next == null) return false;ListNode slow = head;ListNode fast = head.next;int step = 0;while (fast != null && fast.next != null) {System.out.println("Step " + step + ": slow=" + slow.val + ", fast=" + fast.val);if (slow == fast) {System.out.println("Found cycle at step " + step);return true;}slow = slow.next;fast = fast.next.next;step++;}System.out.println("No cycle found after " + step + " steps");return false;
}

2. 可视化链表状态

public void printListState(ListNode head, ListNode slow, ListNode fast) {System.out.print("List: ");ListNode curr = head;Set<ListNode> visited = new HashSet<>();while (curr != null && !visited.contains(curr)) {visited.add(curr);String marker = "";if (curr == slow) marker += "[S]";if (curr == fast) marker += "[F]";System.out.print(curr.val + marker + " -> ");curr = curr.next;}if (curr != null) {System.out.print("(cycle back to " + curr.val + ")");} else {System.out.print("null");}System.out.println();
}

10. 相关题目与拓展

10.1 LeetCode相关题目

1. LeetCode 142. 环形链表 II

题目：找到环形链表中环的起始节点
难度：中等
解法：快慢指针 + 数学推导

2. LeetCode 287. 寻找重复数

题目：在数组中找到重复的数字
难度：中等
解法：将数组看作链表，使用Floyd判圈算法

3. LeetCode 202. 快乐数

题目：判断一个数是否为快乐数
难度：简单
解法：快慢指针检测循环

10.2 算法拓展应用

1. 检测无向图中的环

// 使用DFS检测无向图中的环
public boolean hasCycleInGraph(List<List<Integer>> graph) {int n = graph.size();boolean[] visited = new boolean[n];for (int i = 0; i < n; i++) {if (!visited[i]) {if (dfs(graph, i, -1, visited)) {return true;}}}return false;
}private boolean dfs(List<List<Integer>> graph, int node, int parent, boolean[] visited) {visited[node] = true;for (int neighbor : graph.get(node)) {if (neighbor == parent) continue;if (visited[neighbor] || dfs(graph, neighbor, node, visited)) {return true;}}return false;
}

2. 检测有向图中的环

// 使用DFS和颜色标记检测有向图中的环
public boolean hasCycleInDirectedGraph(List<List<Integer>> graph) {int n = graph.size();int[] color = new int[n]; // 0:白色(未访问), 1:灰色(正在访问), 2:黑色(已完成)for (int i = 0; i < n; i++) {if (color[i] == 0 && dfs(graph, i, color)) {return true;}}return false;
}private boolean dfs(List<List<Integer>> graph, int node, int[] color) {color[node] = 1; // 标记为正在访问for (int neighbor : graph.get(node)) {if (color[neighbor] == 1) { // 发现后向边，存在环return true;}if (color[neighbor] == 0 && dfs(graph, neighbor, color)) {return true;}}color[node] = 2; // 标记为已完成return false;
}

11. 学习建议与总结

11.1 学习建议

1. 理解核心概念

深入理解什么是环形链表
掌握快慢指针的数学原理
理解Floyd判圈算法的应用场景

2. 练习步骤

先掌握HashSet方法（直观易懂）
再学习快慢指针方法（重点掌握）
了解其他方法作为补充

3. 代码实现要点

注意边界条件处理
小心空指针异常
理解不同初始化方式的区别

4. 拓展学习

学习相关的图论算法
掌握其他判圈算法
了解在实际项目中的应用

11.2 知识点总结

核心算法：

HashSet标记法：直观但空间复杂度高
快慢指针法：最优解，空间复杂度O(1)
标记节点法：会修改原数据，不推荐
计数法：依赖数据范围，不够通用

关键技巧：

快慢指针的数学原理
边界条件的正确处理
空指针异常的避免
不同初始化方式的选择

应用场景：

链表环检测
图中环检测
重复数字检测
循环检测问题

11.3 面试要点

1. 基础问题

能够快速实现HashSet方法
理解并实现快慢指针方法
分析时间和空间复杂度

2. 进阶问题

解释快慢指针的数学原理
处理各种边界条件
优化代码性能

3. 拓展问题

如何找到环的起始节点？
如何计算环的长度？
在其他场景中如何应用？

4. 代码质量

代码简洁清晰
边界条件完整
变量命名规范
注释清楚明了

11.4 最终建议

环形链表检测是链表和指针操作的经典问题，也是面试中的高频题目。建议：

重点掌握快慢指针方法：这是最优解，也是面试官最期望看到的解法
理解数学原理：不仅要会写代码，还要能解释为什么这样做
注意代码细节：边界条件和空指针处理是容易出错的地方
练习相关题目：通过更多练习加深理解和应用能力

Java详解LeetCode 热题 100(25):LeetCode 141. 环形链表（Linked List Cycle）详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 环形链表的可视化2.2 核心难点 3. 解法一：HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二：快慢指针法（…...

编程日记 2025/6/5 11:50:22

【仿生机器人】刀剑神域计划——仿生机器人.亚丝娜

我在做仿生机器人头，硬件部分已经搭建完毕，包括头部和颈部，用的23个舵机驱动机器人做表情，也支持头部的旋转（就是颈部的功能），安装了摄像头在眼睛中，还有麦克风接受周围环境声音&…...

编程日记 2025/6/6 3:28:51

代码仓库： https://github.com/siutin/stable-diffusion-webui-docker.git Docker容器地址： https://hub.docker.com/r/siutin/stable-diffusion-webui-docker/tags git clone https://github.com/siutin/stable-diffusion-webui-docker.git cd stabl…...

编程日记 2025/6/5 13:41:23

仓颉项目调试配置与多文件场景下的问题解析

1. 调试配置指南在 VS Code 中配置好仓颉开发工具链后，只需按下 F5 或 Fn F5 即可启动调试。在 CodeArts IDE for Cangjie 中，需先通过右上角的编辑配置 -> 新增配置项 -> 选择 Cangjie (cjdb) Debug -> 选择 launch 模式 -> 点击确认…...

编程日记 2025/6/5 21:15:28

Easyui悬停组件

文章目录一、EasyUI 官方悬停解决方案：Tooltip 组件1. 基础用法2. 高级配置项二、进阶场景：Datagrid 表格悬停扩展1. 监听行事件2. 第三方扩展包（流云大神版） 三、自定义悬停样式四、常见问题解决在EasyUI中，没有直…...

编程日记 2025/6/6 7:21:46

MySQL 8.0 OCP 英文题库解析（十）

Oracle 为庆祝 MySQL 30 周年，截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。从今天开始，将英文题库免费公布出来，并进行解析，帮助大家在一个月之内轻松通过OCP认证。本期公布试题81~90 试题81:…...

编程日记 2025/6/6 0:19:49

Python Pytest

1.Pytest用例发现规则 1.1 模块名(python文件)名必须以 test_ 开头或 _test 结尾，如 test_case，case_test，下划线都不能少 1.2 模块不能放在 . 开头的隐藏目录或者叫 venv的目录下，virtual environment，叫venv1都可以…...

编程日记 2025/6/5 18:20:28

金属膜电阻和碳膜电阻

1、性能比较特性金属膜电阻对比碳膜电阻精度0.1% ~ 1%5% ~ 10%温度系数15 ~ 50 ppm/℃（极低漂移）200 ~ 1000 ppm/℃噪声0.1 μV/V 以下（超低噪声）1~5 μV/V（中高频噪声显著）高频特性寄生电感/电容小&…...

编程日记 2025/6/5 17:48:01

DNS （Domain Name System）域名系统将域名解析为 IP 地址

✅ DNS 服务器是指什么？ **DNS 服务器（Domain Name System Server）是一个将域名（如 www.baidu.com）解析为 IP 地址（如 220.181.38.150）**的服务器。 🧠 一句话理解： DNS…...

编程日记 2025/6/5 23:30:40

如何轻松删除 Android 上的文件（3 种方法）

Android 手机是非常强大的设备，可让我们存储大量的个人数据，从照片和视频到应用程序和文档。然而，随着时间的推移，您的设备可能会因不再需要的文件而变得混乱。删除这些文件有助于释放空间并提高性能。在本指南中，我们…...

编程日记 2025/6/5 11:59:44

[特殊字符] Unity UI 性能优化终极指南 — ScrollRect篇

ScrollRect ManualScrollRect API 我参考了官方最新文档（基于UGUI 3.0包），加上实际性能测试经验，直接给你梳理： 🎯 Unity UI 性能优化终极指南 — ScrollRect篇 🧩 什么是 ScrollRect&#xff…...

编程日记 2025/6/5 14:01:28

自适应流量调度用于遥操作：面向时间敏感网络的通信与控制协同优化框架

英文标题：Adaptive Flow Scheduling for Teleoperation: A Communication and Control Co-Optimization Framework over Time-Sensitive Networks 中文标题：自适应流量调度用于遥操作：面向时间敏感网络的通信与控制协同优化框架作者信息 …...

编程日记 2025/6/5 22:32:13

阿里云服务器-解决宝塔登录不成功

出现问题： This site can’t be reached XX.XX.XXX.XXX took too long to respond. Try: Checking the connection Checking the proxy and the firewall Running Windows Network Diagnostics ERR_CONNECTION_TIMED_OUT 可能是端口未开放原因：服务器…...

编程日记 2025/6/5 11:44:01

6.3 day 35

知识点回顾： 三种不同的模型可视化方法：推荐torchinfo打印summary权重分布可视化进度条功能：手动和自动写法，让打印结果更加美观推理的写法：评估模式可视化理解深度学习网络最重要的2点： 1.了解损失如何定…...

编程日记 2025/6/5 20:40:26

graphviz, dot, Error: lost rA sA edge；独立的模块

1) 有向图dot文件 digraph R { node [shaperecord]; { ranksame rA sA tA } { ranksame uB vB wB } rA -> sA; sA -> vB; t -> rA; uB -> vB; wB -> u; wB -> tA; } 2）出现报警信息 Warning: flat edge between adjacent …...

编程日记 2025/6/5 12:44:17

MicroROS简述

文章目录前言1. 什么是MicroROS2. MicroROS的功能2.1 Micro-ROS 的核心作用：桥梁翻译官2.2 为什么服务端（Agent）能知道设备端的消息和服务？ 3. MicroROS出现的背景3.1 机器人系统的“断层”问题3.2 物联网与边缘计算的兴起3.3 …...

编程日记 2025/6/5 12:38:11

LeetCode Hot100刷题——完全平方数

279. 完全平方数给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而…...

编程日记 2025/6/5 23:35:29

Axure-元件流程图

Axure-02 线框图元件使用目标元件基本介绍基础元件的使用表单型元件的使用菜单与表格元件的使用案例：个人简历表元件基本介绍概述在Axure RP中，元件是构建原型图的基础模块。将元件从元件库里拖拽到画布中，即可添加元件到你…...

编程日记 2025/6/6 0:54:15

LangChain系列之LangChain4j集成Spring Bot

<<< 书接上文 2. 代码示例以下是一个集成 LangChain4j API 的 Spring Boot 应用示例。 2.1 创建 Spring Boot 项目你可以使用SpringInitializr (https://start.spring.io/)来创建一个 Spring Boot 项目。选择 Maven 项目、Java 语言以及合适的 Spring Boot 版本…...

编程日记 2025/6/5 19:23:42

Python爬虫解析动态网页：从渲染到数据提取

一、动态网页与静态网页的区别在开始之前，我们需要理解动态网页与静态网页的区别。静态网页的内容在服务器端是固定的，每次请求都会返回相同的结果，通常以HTML文件的形式存储。而动态网页则不同，其内容是通过JavaScript在客户端…...

编程日记 2025/6/5 23:01:27

LLMs之MCP：如何使用 Gradio 构建 MCP 服务器

LLMs之MCP：如何使用 Gradio 构建 MCP 服务器导读：本文详细介绍了如何使用Gradio构建MCP服务器，包括前提条件、构建方法、关键特性和相关资源。通过一个简单的字母计数示例，演示了如何将Gradio应用转换为LLM可以使用的工具。Gradi…...

编程日记 2025/6/5 17:41:26

VBA模拟进度条

在上一章中我跟大家介绍了ProgressBar控件的使用方法，但由于该控件无法在64位版本的Office中运行，为此我们可以采用Lable控件来模拟进度条的变化，以解决在64位版本的Office中无进度条控件的问题。一、设计思路添加两个重叠的Lable标签控件…...

编程日记 2025/6/5 20:40:20

MySQL强化关键_019_索引优化

目录一、最左前缀原则 1.完全使用索引 2.部分使用索引 3.不使用索引 4.效率折损 （1）使用范围查找 （2）索引断开二、索引失效场景 1. 索引列参与运算 2.索引列模糊查询以“%”开始 3.索引列是字符串类型，查…...

编程日记 2025/6/5 17:50:33

高性能MCU的MPU与Cache优化详解

概述在现代高性能单片机（如ARM Cortex-M7、Cortex-A系列在MCU中的应用）中，Memory Protection Unit (MPU) 和Cache系统的协同工作对系统性能有着决定性影响。本文将深入分析MPU配置如何影响Cache命中率，多主设备对RAM访问的竞争问…...

编程日记 2025/6/5 16:39:53

关于list集合排序的常见方法

目录 1、list.sort() 2、Collections.sort() 3、Stream.sorted() 4、进阶排序技巧 4.1 空值安全处理 4.2 多字段组合排序 4.3. 逆序 5、性能优化建议 5.1 并行流加速 5.2 原地排序 6、最佳实践 7、注意事项前言 Java中对于集合的排序操作，分别为list.s…...

编程日记 2025/6/6 11:55:49

不动产登记区块链系统（Vue3 + Go + Gin + Hyperledger Fabric）

好久没有介绍过新项目的制作了，之前做的一直都是Fisco Bcos的项目，没有介绍过Hyperledger Fabric的项目，这次来给大家分享下。系统概述不动产登记与交易平台是一个基于Hyperledger Fabric的综合性管理系统，旨在实现不动产登记…...

编程日记 2025/6/6 2:44:04

从 GPT 的发展看大模型的演进

这是一个技术爆炸的时代。一起来看看 GPT 诞生后，与BERT 的角逐。 BERT 和 GPT 是基于 Transformer 模型架构的两种不同类型的预训练语言模型。它们之间的角逐可以从 Transformer 的编码解码结构角度来分析。 BERT（Bidirectional Encoder Representatio…...

编程日记 2025/6/5 16:52:41

基于大模型的短暂性脑缺血发作（TIA）全流程预测与诊疗辅助系统详细技术方案

目录系统整体架构系统部署拓扑图核心模块详细技术方案1. 术前风险预测模块算法实现伪代码：数据处理流程：2. 手术方案智能生成系统手术方案决策伪代码：手术方案生成流程：3. 麻醉智能决策系统麻醉方案伪代码：4. 术后监护与复发预测实时监测流程：5. 并发症预测系统双通道风…...

编程日记 2025/6/6 7:01:58

JSCH使用SFTP详细教程

文章目录 1. JSCH和SFTP基础概念1.1 什么是JSCH？1.2 SFTP协议特点1.3 JSCH的优势1.4 常用场景 2. 环境配置和依赖管理2.1 Maven依赖配置2.2 Gradle依赖配置2.3 基础配置类2.4 配置文件示例 3. SFTP连接管理3.1 基础连接类3.2 连接池管理3.3 连接测试工具 4. 文件上传…...

编程日记 2025/6/6 6:39:58

Trae CN IDE 中 PHP 开发的具体流程和配置指南

以下是 Trae CN IDE 中 PHP 开发的具体流程和配置指南，结合知识库内容和实际开发需求整理，并附实例说明：一、安装与初始配置下载与安装 Trae IDE 访问 Trae 官网下载 macOS 或 Windows 版本。安装完成后，启动 Trae，首次运行会进入初始化向导。初始设置主题与语言：选择…...

编程日记 2025/6/5 15:59:58

文章目录

1. 题目描述

1.1 链表节点定义

2. 理解题目

2.1 环形链表的可视化

2.2 核心难点

3. 解法一：HashSet 标记访问法

3.1 算法思路

3.2 Java代码实现

3.3 详细执行过程演示

3.4 执行结果示例

3.5 复杂度分析

3.6 优缺点分析

4. 解法二：快慢指针法（Floyd判圈算法）

4.1 算法思路

4.2 数学原理

4.3 Java代码实现

4.4 另一种实现方式

4.5 详细执行过程演示

4.6 执行结果示例

4.7 复杂度分析

4.8 优缺点分析

4.9 常见错误与注意事项

5. 解法三：标记节点法

5.1 算法思路

5.2 Java代码实现

5.3 优缺点分析

6. 解法四：计数法（暴力解法）

6.1 算法思路

6.2 Java代码实现

6.3 优缺点分析

7. 完整测试用例

7.1 测试用例设计

7.2 性能测试

8. 算法复杂度对比

8.1 时间复杂度对比

8.2 空间复杂度对比

8.3 实际性能测试结果

9. 常见错误与调试技巧

9.1 常见错误

9.2 调试技巧

10. 相关题目与拓展

10.1 LeetCode相关题目

10.2 算法拓展应用

11. 学习建议与总结

11.1 学习建议

11.2 知识点总结

11.3 面试要点

11.4 最终建议

相关文章：