LeetCode 141.环形链表 详细技术解析（含O(1)内存最优解）

LeetCode 141.环形链表 详细技术解析含O(1)内存最优解本文针对LeetCode 141.环形链表问题从题目剖析、基础解法、进阶优化、避坑指南四个维度进行全方位技术拆解结合代码实现、示例验证、复杂度分析帮助开发者彻底掌握该题的核心解题逻辑重点突破进阶要求的O(1)内存复杂度解法适配面试高频考点。题目核心需求判断单链表中是否存在环环的定义某个节点通过连续跟踪next指针可再次到达自身需兼顾时间效率与空间效率尤其需实现进阶要求的常量内存解法。一、题目详情1.1 题目描述给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。如果链表中存在环则返回 true 否则返回 false 。1.2 示例说明示例 1输入head [3,2,0,-4], pos 1输出true解释链表中有一个环其尾部连接到第二个节点索引为1的节点值为2即 -4 的next指向2形成3→2→0→-4→2的环。示例 2输入head [1,2], pos 0输出true解释链表中有一个环其尾部连接到第一个节点索引为0的节点值为1即 2 的next指向1形成1→2→1的环。示例 3输入head [1], pos -1输出false解释链表中只有一个节点next指针为null无环。1.3 提示信息链表中节点的数目范围是 [0, 10⁴]需兼容空链表、单节点、多节点无环/有环等所有场景节点值范围为 -10⁵ ≤ Node.val ≤ 10⁵节点值可能重复无法通过节点值判断是否存在环pos 为 -1无环或者链表中的一个有效索引有环仅用于评测系统标识环的位置不作为函数参数传入进阶要求用 O(1)常量内存解决此问题禁止使用额外的集合、数组等数据结构存储节点。1.4 链表节点定义题目给定# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val x# self.next None二、解题思路拆解环形链表的核心判断难点的是如何避免“无限循环遍历”同时高效识别环的存在。由于链表无法反向遍历且节点值可能重复常规的“遍历对比”思路失效需结合额外逻辑实现判断。本文将讲解两种核心解法覆盖基础入门与进阶最优基础解法哈希表Set存储已遍历节点判断是否重复访问易实现空间复杂度O(n)进阶解法快慢指针龟兔赛跑通过指针速度差判断环的存在满足O(n)时间、O(1)空间最优解。三、基础解法实现易理解适合入门3.1 思路说明核心逻辑利用哈希表Python中的Set的“不可重复”特性遍历链表时将每个节点存入Set中若遍历过程中发现当前节点已存在于Set中说明该节点被重复访问即链表存在环若遍历至链表末尾next为null则无环。步骤初始化一个空的Set用于存储已遍历的链表节点初始化当前指针cur指向链表头节点head循环遍历链表若cur为null说明遍历到链表末尾无环返回false若cur已在Set中说明存在环返回true若cur不在Set中将cur加入Setcur移动至cur.next继续遍历。3.2 代码实现# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val x# self.next NonefromtypingimportOptionalclassSolution:defhasCycle(self,head:Optional[ListNode])-bool:# 初始化哈希表存储已遍历的节点visitedset()curhead# 循环遍历链表whilecur:# 若当前节点已存在说明有环ifcurinvisited:returnTrue# 否则加入哈希表继续遍历visited.add(cur)curcur.next# 遍历到末尾cur为null无环returnFalse3.3 复杂度分析时间复杂度O(n)最坏情况下需遍历链表所有节点无环时每个节点的访问、哈希表的添加和查询操作均为O(1)总时间为O(n)空间复杂度O(n)哈希表需存储链表所有节点无环时占用额外O(n)内存不满足进阶要求但胜在逻辑简单、易调试适合面试快速上手。3.4 示例验证示例1head [3,2,0,-4], pos 1 → 遍历节点3→2→0→-4→2当遍历到第二个2时发现2已在visited中返回true示例2head [1,2], pos 0 → 遍历节点1→2→1当遍历到第二个1时发现1已在visited中返回true示例3head [1], pos -1 → 遍历节点1→nullcur为null返回false。3.5 避坑点避免存储节点值节点值可能重复如多个节点值为2若存储节点值而非节点本身会导致误判如无环链表中存在相同值节点会误认为有环空链表处理当head为null时直接返回false代码中while cur会直接跳过循环无需额外添加判断。四、进阶解法实现O(1)内存最优解进阶要求禁止使用额外哈希表/数组核心思路是“快慢指针法”又称龟兔赛跑算法通过两个速度不同的指针遍历链表若链表存在环快指针终将追上慢指针若不存在环快指针会先遍历到链表末尾。4.1 核心思路拆解指针初始化定义两个指针slow慢指针龟和fast快指针兔均从head开始指针移动规则慢指针每次走1步slow slow.next快指针每次走2步fast fast.next.next环的判断逻辑若链表无环快指针会先到达链表末尾fast为null或fast.next为null此时返回false若链表有环快指针会进入环中循环慢指针也会进入环中由于快指针速度是慢指针的2倍终将追上慢指针即slow fast此时返回true。4.2 关键细节避坑点循环条件设置必须判断fast和fast.next是否为null避免快指针移动时出现空指针异常如fast为null时执行fast.next会报错指针速度差必须是“慢1步、快2步”若速度差为1如慢1、快1指针永远不会相遇若速度差过大如慢1、快3可能会跳过慢指针增加判断周期空链表与单节点处理head为null空链表或head.next为null单节点直接返回false无需进入循环。4.3 代码实现完整最优解# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val x# self.next NonefromtypingimportOptionalclassSolution:defhasCycle(self,head:Optional[ListNode])-bool:# 特殊情况空链表或单节点无环ifnotheadornothead.next:returnFalse# 初始化快慢指针均从head开始slow,fasthead,head# 循环条件fast和fast.next不为null避免空指针whilefastandfast.next:# 慢指针走1步快指针走2步slowslow.nextfastfast.next.next# 若快慢指针相遇说明有环ifslowfast:returnTrue# 循环结束fast到达末尾无环returnFalse4.4 复杂度分析时间复杂度O(n)分两种情况无环场景快指针遍历到链表末尾时间为O(n/2) ≈ O(n)有环场景慢指针进入环后快指针最多再走1圈即可追上慢指针总时间仍为O(n)。空间复杂度O(1)仅使用slow、fast两个指针变量无任何额外空间占用完全满足进阶要求是面试中的最优解法。4.5 示例验证示例1head [3,2,0,-4], pos 1初始slow3fast3第1步slow2fast0第2步slow0fast2第3步slow-4fast0第4步slow2fast2 → 相遇返回true。示例2head [1,2], pos 0初始slow1fast1第1步slow2fast1 → 相遇返回true。示例3head [1], pos -1 → 进入特殊判断直接返回false。五、常见问题与避坑指南5.1 空指针异常问题高频坑问题场景循环条件写错仅判断fast不为null未判断fast.next导致fast为最后一个节点时执行fast.next.next报错。解决方案循环条件必须写为while fast and fast.next确保fast和fast.next均不为null时才执行指针移动操作。5.2 快慢指针速度设置错误问题场景将快指针速度设为3步、慢指针设为1步导致快指针跳过慢指针无法相遇误判为无环。解决方案严格遵循“慢1步、快2步”的速度差这是保证两指针必相遇有环时的核心也是该算法的标准实现方式。5.3 单节点与空链表处理遗漏问题场景未添加特殊判断当head为null或head.next为null时进入循环导致空指针异常或误判。解决方案代码开头添加if not head or not head.next: return False直接处理空链表和单节点场景避免无效循环。5.4 混淆“节点值相等”与“节点本身相等”问题场景判断快慢指针是否相遇时误写为if slow.val fast.val而非if slow fast导致节点值相同时误判为有环。解决方案必须判断“指针指向的节点本身是否相等”而非节点值因为链表中可能存在多个值相同但地址不同的节点。六、总结与拓展6.1 解法对比解法时间复杂度空间复杂度优点缺点基础解法哈希表O(n)O(n)逻辑简单、易实现、易调试适合入门占用额外内存不满足进阶要求大数据量下可能内存紧张进阶解法快慢指针O(n)O(1)内存最优性能稳定面试高频考点逻辑稍抽象需注意指针速度和循环条件的设置6.2 面试建议面试时建议先讲解基础解法哈希表快速展示解题思路和代码实现能力再讲解进阶解法快慢指针重点说明算法原理龟兔赛跑、指针移动规则和避坑细节体现性能优化意识。面试官常追问“为什么快慢指针一定能相遇” 可回答“有环时快指针在环内循环慢指针进入环后两者的距离会逐渐缩小每次缩小1步最终必然相遇不会出现永远追不上的情况。”6.3 拓展思考若题目进阶不仅判断是否有环还需找到环的入口节点该如何修改快慢指针解法—— 当快慢指针相遇后将慢指针重置为head两者同时以1步/次的速度移动再次相遇的节点即为环的入口若链表节点数极大10⁴节点两种解法的性能差异—— 快慢指针解法无额外内存占用避免内存溢出运行效率更稳定哈希表解法会占用10⁴个节点的内存性能略逊若节点值唯一能否通过节点值判断环—— 可以但不推荐因为题目未保证节点值唯一且这种方法的通用性差面试中优先使用快慢指针或哈希表解法。