教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇文章以《算法通关手册》AlgoNote仓库中的 0141. 环形链表题解 为主体结合仓库内 链表基础、链表双指针 等配套教程与 LinkedList 源码系统讲解判断单链表是否存在环这一经典面试题的两种标准解法哈希表标记法与快慢指针Floyd 判圈算法。读完本文你将掌握两种解法的完整可运行代码、复杂度分析、边界条件处理并理解 Floyd 判圈算法相遇的数学原理及其在寻找环入口问题LeetCode 142中的延伸应用。一、题目概述题目编号0141. 环形链表力扣 Linked List Cycle标签哈希表、链表、双指针难度简单1.1 题目大意描述给定一个链表的头节点head。要求判断链表中是否有环。如果有环则返回True否则返回False。说明数据范围链表中节点的数目范围是 $[0, 10^4]$$-10^5 \le Node.val \le 10^5$pos为-1或者链表中的一个有效索引pos仅用于说明环的入点位置并不作为参数传入函数。示例示例 1head [3,2,0,-4], pos 1输出True。解释链表中有一个环其尾部连接到第二个节点。示例 2head [1,2], pos 0输出True。解释链表中有一个环其尾部连接到第一个节点。1.2 前置知识链表的节点结构在阅读解法代码之前先明确链表节点的定义。仓库源码 linked_list.py 中定义的ListNode类与 LeetCode 平台给出的定义完全一致class ListNode: def __init__(self, val0, nextNone): self.val val self.next next每个节点包含两个成员val节点存储的值和next指向下一个节点的指针。判断链表是否有环本质上是判断沿next指针遍历时是否会再次访问到已经出现过的节点。关于链表结构、创建、遍历等更多基础操作可参考仓库的 链表基础教程。二、思路 1哈希表标记已访问节点2.1 思路讲解最简单的思路是遍历所有节点每次遍历到一个节点之前先使用哈希表Python 中的set判断该节点是否已被访问过。如果该节点已经在哈希表中说明链表存在环直接返回True如果不在哈希表中则将该节点加入哈希表继续向后遍历。由于链表节点对象在内存中具有唯一性当环存在时遍历必然绕回某个已记录过的节点对象从而被哈希表捕获。2.2 完整代码class Solution: def hasCycle(self, head: ListNode) - bool: nodeset set() while head: if head in nodeset: return True nodeset.add(head) head head.next return False2.3 复杂度分析时间复杂度$O(n)$。最坏情况下遍历链表所有节点一次其中 $n$ 为链表节点数。空间复杂度$O(n)$。哈希表需要存储所有已访问节点节点数为 $n$ 时占用 $O(n)$ 额外空间。哈希表思路直观、代码短小是以空间换时间的典型代表也最容易理解和实现。三、思路 2快慢指针Floyd 判圈算法3.1 思路讲解龟兔赛跑这种方法类似于在操场跑道跑步两个人从同一位置同时出发如果跑道有环环形跑道那么速度更快的一方总能追上慢的一方。基于上述想法Floyd 判圈算法使用两个指针慢指针龟每次前进一步即slow slow.next快指针兔每次前进两步即fast fast.next.next两步或多步效果是等价的。判定逻辑如果两个指针在链表头节点以外的某一节点相遇即相等说明链表有环否则如果快指针到达了某个没有后继指针的节点fast None或fast.next None说明链表无环。这一技巧在仓库的 链表双指针教程 中被归纳为步长不一致的快慢指针慢指针每次移动 1 步、快指针每次移动 2 步可用于找中点、检测环、找交点等场景。3.2 完整代码class Solution: def hasCycle(self, head: ListNode) - bool: if head None or head.next None: return False slow head fast head.next while slow ! fast: if fast None or fast.next None: return False slow slow.next fast fast.next.next return True3.3 关键细节解析这段代码中有几个细节值得注意提前判空如果head为空或只有一个节点head.next None不可能存在环直接返回False。这既避免了空指针访问也覆盖了最短无环链表的情形。初始化错开一步slow指向headfast指向head.next而不是都指向head。这样两者起点错开循环条件slow ! fast才能在无环情况下正常推进如果两者都从头出发且while slow ! fast一开始就相等循环会直接跳过。循环内先判快指针每次迭代先检查fast或fast.next是否为None一旦快指针到达链表末尾说明无环返回False。相遇即返回当slow fast跳出循环时说明两指针相遇于环内某节点链表有环返回True。3.4 为什么两个指针必定相遇从数学上可以证明相遇的必然性假设链表无环快指针每次多走一步必然率先到达末尾假设链表有环则快指针进入环后相对慢指针而言每次迭代两者的距离都会缩短 1 步快指针每次前进 2 步、慢指针前进 1 步相对速度差为 1 步/迭代。因此在一圈之内快指针必定追上慢指针两者必然相遇。该结论同样保证了时间复杂度为线性。3.5 复杂度分析时间复杂度$O(n)$。快慢指针最多遍历链表长度加环长整体仍为线性复杂度。空间复杂度$O(1)$。只使用了slow、fast两个指针无需额外存储是常数级空间。四、两种思路对比与选择建议对比维度哈希表标记法快慢指针Floyd 判圈核心思想用额外集合记录已访问节点双指针速度差制造相遇时间复杂度$O(n)$$O(n)$空间复杂度$O(n)$$O(1)$实现难度低直观易写中需注意初始化与边界是否修改链表否否典型场景允许线性空间追求稳妥面试常考空间敏感场景首选选择建议哈希表解法胜在直白、不易出错适合作为第一反应的保底方案快慢指针解法空间复杂度仅为 $O(1)$是算法面试中更被看重的优化方向也是链表双指针这一知识点的代表性应用。仓库的 链表双指针教程 将该解法列为步长不一致快慢指针的典型场景建议优先掌握。五、延伸进阶找到环的入口LeetCode 142 环形链表 II判断是否有环只是第一步高频追问是找到入环的第一个节点即 LeetCode 142 环形链表 II仓库中已有对应题解 linked-list-cycle-ii.md。5.1 相遇后的数学推导假设入环位置为A快慢指针在环内B点相遇则相遇时慢指针走了 $a b$ 步链表头到入环点距离为 $a$入环点到相遇点距离为 $b$快指针走了 $a n(bc) b$ 步$c$ 为相遇点继续走到入环点的距离$n$ 为快指针绕环的圈数。因为快指针走的步数是慢指针的两倍即 $2(ab) a n(bc) b$可推出$$a c (n-1)(bc)$$结论从链表头部到入环点的距离 $a$等于从相遇点到入环点的距离 $c$ 加上 $n-1$ 圈环长。也就是说在快慢指针相遇后让一个新指针ans从链表头部出发、慢指针从相遇点出发两者每次各走一步它们相遇的位置就是环的入口。5.2 完整代码class Solution: def detectCycle(self, head: ListNode) - ListNode: fast, slow head, head while True: if not fast or not fast.next: return None fast fast.next.next slow slow.next if fast slow: break ans head while ans ! slow: ans, slow ans.next, slow.next return ans该解法时间复杂度 $O(n)$、空间复杂度 $O(1)$与判断是否有环共享同一套快慢指针思想是 141 题的天然延伸建议一并刷透。六、总结与相关练习本文围绕 0141. 环形链表 给出了两条完整可运行的解题路径哈希表标记法$O(n)$ 时间、$O(n)$ 空间与 Floyd 判圈快慢指针法$O(n)$ 时间、$O(1)$ 空间并深入讲解了快慢指针相遇的必然性与寻找环入口的数学推导。掌握这一题后建议继续完成以下同族题目以巩固链表双指针技能0142. 环形链表 II寻找环入口0019. 删除链表的倒数第 N 个结点起点不一致的快慢指针0206. 反转链表0234. 回文链表更完整的刷题规划可参考仓库的 链表基础题目列表 与 链表双指针题目列表从中可以找到环形链表、链表中点、链表交点等全套双指针经典问题的题解索引。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 142. 环形链表 II哈希表与快慢指针Floyd 判圈双解法详解LeetCode 142. 环形链表 II哈希表与快慢指针Floyd 判圈双解法详解 导读 本文讲解 LeetCode 142. 环形链表 II 的两种经文档教程知识库AlgoNote 算法通关手册LeetCode 142「环形链表 II」—— 用快慢指针Floyd 判圈算法定位环入口的推导、实现与复杂度分析AlgoNote 算法通关手册LeetCode 142「环形链表 II」—— 用快慢指针Floyd 判圈算法定位环入口的推导、实现与复杂度分析 本文是「算教程文档知识库AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析 本篇技术指南围绕 LeetCode 第 00教程文档知识库上一篇突破数据集限制MAE模型如何在CIFAR-100与Fashion-MNIST上实现高精度迁移下一篇如何快速部署T3Q-ko-solar-dpo-v5.0-openmind5分钟完成韩语AI模型推理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考