【忍者算法】从公路跑步到链表成环：探索环形链表检测｜LeetCode第141题 环形链表
从公路跑步到链表成环：探索环形链表检测生活中的环形
想象两个人在环形跑道上跑步，一个跑得快，一个跑得慢。如果他们一直跑下去，快的跑者一定会从后面追上慢的跑者。这就是我们今天要讨论的环形链表问题的现实映射。在跑道上，两个速度不同的跑者相遇就说明跑道是环形的；同样在链表中，如果两个速度不同的指针相遇，就说明链表中存在环。
问题描述
LeetCode第141题"环形链表"要求：给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
例如：
输入：3 → 2 → 0 → -4 ↑___________|输出：true解释：链表中存在一个环，尾节点连接到第二个节点输入：1 → 2 ↑___|输出：true解释：链表中存在一个环，尾节点连接到第一个节点输入：1 → 2 → 3 → 4输出：false解释：链表中不存在环简单解法：哈希表记录
最直观的想法是用一个哈希表记录每个走过的节点。就像在跑道上撒面包屑，如果遇到已经撒过面包屑的地方，说明路径形成了环。
哈希表解法实现
public boolean hasCycle(ListNode head) { Set<ListNode> seen = new HashSet<>(); while (head != null) { // 如果已经见过这个节点，说明有环 if (seen.contains(head)) { return true; } // 记录当前节点 seen.add(head); head = head.next; } return false;}优化解法：快慢指针（Floyd判圈算法）
这个经典算法也被称为"龟兔赛跑算法"，就像我们开始说的跑步场景：让一快一慢两个指针在链表上移动，如果存在环，快指针最终一定会追上慢指针。
为什么快慢指针一定会相遇？
想象在环形跑道上：
[*]快指针每次走2步，慢指针每次走1步
[*]相对来说，快指针每次都在追赶慢指针1步
[*]如果有环，这就像在操场上追赶，快指针一定会追上慢指针
[*]如果无环，快指针会先到达终点
代码实现与详解
public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } // 初始化快慢指针 ListNode slow = head; ListNode fast = head; // 快指针每次走两步，慢指针每次走一步 while (fast != null && fast.next != null) { slow = slow.next; // 慢指针走一步 fast = fast.next.next; // 快指针走两步 // 如果两个指针相遇，说明有环 if (slow == fast) { return true; } } // 如果快指针到达链表末尾，说明无环 return false;}图解过程
以一个有环链表为例：
1) 初始状态：3 → 2 → 0 → 4 ↑_________|S,F(S=slow, F=fast)2) 第一次移动后：3 → 2 → 0 → 4 ↑_________| S F3) 第二次移动后：3 → 2 → 0 → 4 ↑_________| S F4) 最终相遇：3 → 2 → 0 → 4 ↑_________| S,F复杂度比较
哈希表解法：
[*]时间复杂度：O(n)
[*]空间复杂度：O(n)，需要存储已访问节点
[*]优点：思路直观，容易实现
[*]缺点：需要额外空间
快慢指针解法：
[*]时间复杂度：O(n)
[*]空间复杂度：O(1)，只需要两个指针
[*]优点：空间效率高，实现优雅
[*]缺点：需要理解快慢指针的数学原理
核心原理解析
1. 数学证明
为什么快慢指针一定会相遇？
[*]假设环长为K，入环前长度为N
[*]慢指针走S步时，快指针走2S步
[*]快指针多走的S步一定是环长K的整数倍
[*]因此快慢指针一定会在入环后的K-N步内相遇
2. 临界情况分析
[*]空链表
[*]单节点链表
[*]环的长度为1（自环）
[*]入环点在开头或结尾
实用技巧总结
解决环形问题的关键点：
[*]掌握快慢指针技巧
[*]理解环形结构的特性
[*]考虑边界情况
[*]注意指针移动的顺序
相关的环形问题：
[*]找到环的入口点
[*]计算环的长度
[*]找到环中的特定节点
小结
环形链表的检测问题是链表操作中的一个经典问题。它教会我们：
[*]如何用最小的空间解决复杂问题
[*]快慢指针这个强大的算法技巧
[*]如何将现实问题映射到算法思维
[*]优雅解法往往来自于深刻的数学原理
建议：多思考快慢指针的应用场景，它不仅用于检测环，还可以：
[*]找到链表中点
[*]判断链表是否为回文
[*]找到倒数第K个节点
这些问题都可以用类似的思维方式来解决！
<hr>作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
页:
[1]