力扣141环形链表：哈希表与快慢指针，一次讲清判环与面试变种

前阵子有个学弟跟我吐槽说力扣141环形链表这题看着简单结果提交了三次都超时。我一看他的代码好家伙他遍历链表的时候顺便打印了每一个节点的值链表有环当然就永远打印不完了。这题在力扣热题100里属于“入门必写”的链表题但真正能一次提交通过、并且面对追问不慌的人其实不多。环形链表考的不只是判断逻辑还有你对引用、循环、复杂度和数学推导的理解。今天我就以这道题为例把哈希表、快慢指针、边界坑、面试变种一次讲清楚适合刚刷链表的新手也适合想补全证明细节的进阶选手。1. 先把题目彻底拆开环形链表在考什么1.1 题目到底长什么样力扣141的题面非常简洁给定一个链表的头节点head判断链表中是否有环。所谓有环就是链表中某个节点的next指针指向了它之前出现过的某个节点导致从那个位置往后遍历永远走不到None。函数签名是def hasCycle(self, head: Optional[ListNode]) - bool返回True表示有环返回False表示无环。力扣网页上的示例里会带上一个pos参数比如head [3,2,0,-4], pos 1。这里的意思不是让你在函数里读取pos它只是描述测试用例构造环的方式最后一个节点-4的next指向下标为 1 的节点2于是链表形成了一个从2出发、经过0、-4再回到2的环。你提交的代码只拿得到head一个参数所以千万别指望通过读取pos来投机取巧。很多人第一次做这题时会下意识把链表和数组混为一谈。数组的遍历到尽头就停了链表却会因为一个额外的指向变得没有尽头。理解这一点的关键是明白链表节点之间靠的是“对象引用”而不是单纯的值传递。题目给的head是一个引用沿着next能走到的节点集合就是这个链表真正覆盖的内存区域。一旦某个节点的next指回了集合里的老节点你就进入了一个无限循环。1.2 为什么“环”是链表题目里的经典坑链表相关题目在刷题攻略里通常被安排在入门阶段但环形链表的坑一点不少。第一个坑是“如何判断遍历会不会停下来”。正常链表遍历到None就结束了你可以写一个简单的while cur:循环但有环的情况下这个循环永远不满足退出条件如果没有额外的检测机制程序会一直空转直到资源耗尽。第二个坑是“如何在不修改原链表的前提下做判断”。有的新手想用“把访问过的节点标记一下”这种思路但对于链表节点来说你很难像数组那样给节点打个标除非额外用哈希表记录。哈希表确实能解决问题空间复杂度却是 O(n)一旦遇到百万级链表内存开销就成了问题。面试官往往看到这里就会追问一句“能不能只用 O(1) 的空间”这就是快慢指针登场的时机。第三个坑是“这道题虽然小但它是一堆难题的基石”。环形链表 II、寻找重复数、求环长度、判断两个链表是否相交全都建立在“怎么高效判环”这个基础能力上。所以刷题不要只满足于把 141 通过还要理解背后的数学原理。我自己带新人时经常说环形链表这题如果不能手写并讲清楚证明后面遇到环入口、重复数、双链表相交这类变种大概率会卡壳。2. 解法选型从哈希表到快慢指针别急着写代码2.1 哈希表方案最自然的暴力思路拿到这道题绝大多数人的第一反应是“走一个记一个”。具体做法是准备一个空的哈希集合seen从head开始遍历每到一个节点先判断它是否已经在seen里。如果在说明这个节点之前被访问过链表有环如果不在就把当前节点加入集合再移动到下一个节点。一直遍历到None就说明链表没有环返回False。这个方案的时间复杂度是 O(n)因为每个节点最多被访问一次。空间复杂度是 O(n)因为你需要把每个节点都存进集合里。在力扣的测试数据里这个解法通常能通过但在面试中当面试官追问“能不能只用一个常数级别的额外空间”时你如果只会这一招就会显得准备不足。所以哈希表只适合作为一道“保底思路”而不是最终答案。哈希表方案还有一个很容易踩的坑节点判重时不能使用节点的val必须使用节点对象本身。链表里允许不同节点拥有相同的值比如一个无环链表[1,2,2,3]其中有两个节点的值都是 2但它们是两个不同的对象。如果你用val来判断是否访问过会错误地认为第二个值为 2 的节点造成了环。力扣的测试用例里经常会埋这种“值重复”陷阱新手很容易被绕进去。2.2 快慢指针O(1)空间的经典方案快慢指针也叫 Floyd 判圈算法是判断链表是否有环最经典的方法。核心思路是定义两个指针slow和fast初始时都指向head然后开始循环。慢指针每次走一步快指针每次走两步。如果链表没有环快指针会先到达None循环正常退出返回False。如果链表有环那么快指针进入环后会在环内不断追赶慢指针最终两者指向同一个节点返回True。这就像两个人在圆形操场跑步甲的速度是乙的两倍。只要跑道的形状是闭合的哪怕两人同时从同一个位置出发速度快的甲也会在某一圈里从后面追上乙。链表里的“环”就相当于闭合跑道fast的移动速度是slow的两倍所以追上是必然的。整个过程只需要两个指针变量没有使用任何额外数据结构空间复杂度严格为 O(1)。为什么快指针每次要走两步而不是走一步如果快慢指针速度相同它们会永远保持距离不变永远不可能相遇。要形成“追及”快指针必须比慢指针快至少一步。每次快指针多走一步相对距离就缩短一步。步长选 2 是最常见的选择因为实现简单证明也最清晰。选 3 或更大的步长理论上也能追上但代码里对fast.next.next.next的判空会变得格外麻烦还容易在边界条件下出错所以面试时没必要冒险。2.3 关键证明为什么快指针一定能追上慢指针这里我要把证明写慢一点因为这是面试官最喜欢深挖的地方。假设链表有环慢指针在某个时刻第一次进入环。此时快指针由于速度快可能已经绕着环走了好几圈但无论如何它一定也在环内某个位置。设环的长度为 L慢指针刚进入环时按照慢指针前进的方向来看快指针领先慢指针 d 个节点。因为快快指针都在环内所以 d 一定满足 0 d L而且如果追赶方向反了你可以理解为快指针距离追上慢指针还差 L-d 步但最终总能追到。由于快指针每一步比慢指针多走一个节点它们之间的相对距离每轮会减少 1。经过最多 L 步之后快指针一定能追上慢指针。这个过程一定发生在慢指针在环内走完一整圈之前因为 d 的最大值是 L-1。所以从时间效率上快慢指针在有环情况下的总移动步数不会超过慢指针从head到入环点的距离 a 加上环长 L整体仍然是一个 O(n) 的算法。如果链表没有环那更简单。快指针每次走两步它一定比慢指针更早碰到None。你只需要在循环里检查fast和fast.next是否为空只要有一个为空说明链表已经走到头了没有环马上返回 False。这也是快慢指针在无环情况下能自动终止的关键。理解了这个证明你就能解释为什么快慢指针永远不会错过环也就能自信面对面试官的“为什么不是死循环”这个问题。3. 代码落地Python实现的完整过程与细节3.1 手写前置环境链表节点的定义力扣的环境里已经帮你定义好了ListNode但在本地练习和面试手写时你需要自己把它写出来。定义非常简单class ListNode: def __init__(self, x): self.val x self.next None每个节点只有两个字段val保存节点值next保存指向下一个节点的引用。在环形链表题目里节点值本身没什么意义真正有意义的是节点之间的引用关系。这也解释了为什么不能用“值相等”来判断环值相同的两个节点可能是完全不同的对象。如果你要在本地构造一个带环的链表可以这样写a ListNode(3) b ListNode(2) c ListNode(0) d ListNode(-4) a.next b b.next c c.next d d.next b # 让尾节点指回第二个节点形成环构造完这组节点后从a出发遍历会一直沿着a - b - c - d - b - c - d - ...无限循环。你用这个结构来测试hasCycle(a)应该得到True。3.2 哈希表版实现10分钟搞定但不够省这里先给出哈希表版本的完整代码方便你对比def hasCycle(self, head: ListNode) - bool: seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False这段代码有两个关键点。第一cur in seen判断的是节点对象是否已经存在。Python 的set在存储自定义对象时默认使用对象的id作为哈希依据所以两个不同节点哪怕值相同也会被当成两个不同元素不会误判。第二seen.add(cur)必须在移动cur之前完成否则如果链表只有两个节点且第二个节点指向第一个节点你会在进入下一轮前丢失对第一个节点的记忆最终漏判。从代码量上讲这个版本比快慢指针更短逻辑也很直接。但它唯一的缺点就是空间。面试官通常不会直接否定而是会追问一句“你有没有更省空间的办法”。如果你能马上接住快慢指针方案这段哈希表代码反而可以成为你展示“先暴力再优化”思路的好素材。3.3 快慢指针版实现最优解的标准写法回到最优解我推荐你使用下面这个写法它是我在刷了大量题之后觉得最不容易出错的一版def hasCycle(self, head: ListNode) - bool: if not head or not head.next: return False slow head fast head.next while slow ! fast: if not fast or not fast.next: return False slow slow.next fast fast.next.next return True为什么这里把fast初始化为head.next因为这样可以保证循环一开始slow和fast就不相等不用额外处理“它们初始就在同一点”的情况。循环内部先用if not fast or not fast.next判断快指针下一步能不能安全走如果不能说明链表没环直接返回 False。如果安全就同时移动两个指针一个走一步一个走两步。另一种更普遍的写法是两个指针都从head出发循环条件用while fast and fast.next然后每次移动完再判断slow fast。这种写法同样没问题我也经常在题解里看到。但如果你在面试时神经紧张我建议用我上面给出的那版因为循环结构更简单判断条件和指针移动的配合更线性不太容易写乱。3.4 一行代码写法与性能陷阱力扣讨论区里经常看到一种非常紧凑的写法def hasCycle(self, head: ListNode) - bool: slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这版代码看着很爽但有一个隐藏的“性能陷阱”需要你注意它把slow和fast的移动放在判断相遇之前也就是说第一轮循环必先移动。如果链表只有一个节点且它指向自己那么slow和fast同时移动到唯一节点然后判断相等返回 True。这没问题。但如果链表的head本身就是环入口且你用的是上面这种“先移动再判断”的写法第一轮就会移动fast两步中途需要访问fast.next.next此时必须保证fast.next不为空。所以循环条件里的fast and fast.next不是随便写的它和fast fast.next.next是一对固定搭配。另一个常见错误是为了“简化代码”而让fast也每次走一步这会让两个指针的相对速度变成 0永远无法相遇。写代码之前先在心里确认速度差是否为 1。一旦速度差为 0整个算法就失效了而且这类错误很难通过测试用例发现因为小的有环链表可能碰巧在某种条件下用错误方式也能通过但遇到某些环位置就会挂。提示本地调试有环链表时绝对不要大量打印节点值。一旦链表有环打印操作会让程序陷入死循环把 IDE 卡死。你可以设置一个计数器辅助输出几次后就 break或者干脆用调试器断点观察循环次数。4. 边界条件与逼疯人的坑我在提交时踩过的雷4.1 空链表和单节点链表是最容易翻车的入口力扣的函数签名支持head为None也支持只有一个节点的链表。很多第一次写快慢指针的人只记得判断if head is None却忘了head.next也可能是None。如果他们采用了fast head.next的写法那一开始fast就是None后续根本没法访问fast.next。我在带新人时发现最稳定的习惯是在函数开头写一行if not head or not head.next: return False这行代码同时处理了空链表和单节点链表两种情况。单节点链表如果无环head.next为None直接返回 False如果它有环必然是head.next head但按照这个特判它也会被返回 False这显然是错的等等题目中一个节点也可以成环比如node.next node。力扣的测试用例可能会包含这种情况。如果not head.next无法区分单节点有环还是无环实际上单节点有环时head.next head不是 None所以not head.next为 False不会返回会继续执行。但head.next不是 None。OK。所以这个特判是安全的单节点有环时head.next非 None不返回 False。那么用if not head or not head.next对单节点有环会跳过不head.next是节点本身非 None所以条件不成立继续。正确。我们还要注意如果单节点有环且采用slowhead, fasthead.next初始化fast为同一个节点slow ! fast? 不相等因为 fast 指向同一个节点但对象相同slow fast为 True? 注意fast head.next而head.next head所以fast是headslow也是head所以slow ! fast为 False循环不进入然后return True。正确。所以这版可以处理自环。为了安全一些题解甚至不特判单节点无环直接进入循环也能过但特判让逻辑更清晰。4.2 死循环的元凶指针移动顺序写错我最初写快慢指针时犯过一个特别隐蔽的错。我把移动和相等判断的顺序写成了“先移动 fast再移动 slow最后判断”但循环条件用的是while fast and fast.next。本来这样也没问题因为循环条件已经保证了 fast 可以安全走两步。真正的问题出在另一版“先移动再判断循环条件”的写法上比如这样while True: fast fast.next.next slow slow.next if fast slow: return True if fast is None: return False看着似乎能工作但一旦链表无环fast.next.next在倒数第二步时就会访问空指针。所以正确做法是先检查fast and fast.next再移动再判断相遇。这也是我在推荐代码里把if not fast or not fast.next: return False放在移动前面的原因。还有一次我在大循环里不小心把slow slow.next写成了slow fast结果速度差丢失程序陷入真正的死循环。这类低级错误靠眼睛很难发现建议写完代码后先走一遍简单的示例再走一遍边界示例确认每一步的指针指向是否符合预期。4.3 构造心爱测试用例手写一个带环链表如果你想在本地练习千万别只依赖力扣网页。自己写测试用例能让你更深刻地理解环的结构。构造带环链表的通用方法是先按顺序把n个节点串起来再选择一个节点下标pos把最后一个节点的next指向下标为pos的节点。例如def build_linked_list(values, pos): nodes [ListNode(v) for v in values] for i in range(len(nodes) - 1): nodes[i].next nodes[i 1] if pos 0: nodes[-1].next nodes[pos] return nodes[0]这样build_linked_list([3,2,0,-4], 1)就对应力扣示例。如果是无环链表pos传-1即可。我习惯在本地一次性测试至少三组用例空链表、单节点无环、单节点自环、长链无环、长链带环。这样基本能覆盖所有让新手翻车的情况。4.4 常见问题速查表现象可能原因解决办法空链表或单节点无环报错没有在开头处理head.next为空加一行if not head or not head.next: return False访问fast.next.next抛异常没检查fast.next是否为空循环条件写while fast and fast.next有环却返回 False移动或判断顺序不对先检查快指针可走再移动最后判断相遇本地调试死循环打印节点值导致卡死设置计数器或移除打印判断错误值重复用节点值而非对象判重哈希表存node本身不要存node.val这张表是我从自己和身边人的报错里总结出来的基本覆盖了力扣评论区常见问题。当然真实刷题时你还可能遇到一些奇怪的超时通常都是因为某个分支忘记更新指针导致实际遍历没有前进。遇到这种问题先把代码逻辑在纸上画一遍永远比盯着屏幕发呆有效。5. 面试官最爱问的变种从141到142及其他5.1 升级打怪环形链表II如何找入口力扣 142 是 141 的直接升级版本它要求返回环的入口节点而不仅仅是判断有没有环。解法同样基于快慢指针分为三步第一步用快慢指针找到第一次相遇点第二步把快指针重新放到head并且把快指针的速度改为每次走一步第三步两个指针继续同时每次走一步它们再次相遇的地方就是环入口。为什么能这样找入口我来推导一下。设链表头到环入口的距离为a入口到第一次相遇点的距离为b相遇点继续走到入口的距离为c。环长L b c。第一次相遇时慢指针走了a b快指针走了a b k * L因为快指针速度是慢指针的 2 倍所以有2 * (a b) a b k * L a b k * L a k * L - b (k - 1) * L c这个式子的意思是从链表头走到环入口的距离a等于从第一次相遇点继续走到入口的距离c外加若干圈。所以一个指针从head出发另一个从相遇点出发都以步长 1 前进必然在环入口相遇。面试时如果能白板写出这个推导印象分会高不少。5.2 追问如何计算环的长度如果面试官继续追问环的长度也有简便方法。在快慢指针第一次相遇后让其中一个指针停在原地另一个指针以每次走一步的速度继续绕环同时用一个计数器统计步数。当指针重新回到起点时计数器显示的值就是环长。这个方法的原理是第一次相遇点一定在环内从环内任意一点出发沿next走一圈必然回到自身。所以计数器统计的就是完整的环长不需要额外知道环入口在哪里。时间复杂度 O(L)空间复杂度 O(1)。如果你不追求极致空间也可以用哈希表记录每个节点的访问顺序当遇到重复节点时用当前步数减去该节点第一次出现时的步数也能得到环长但面试时快慢指针方案往往更受欢迎。5.3 快慢指针还能用在哪些地方快慢指针不只在链表里有价值。力扣 287 题“寻找重复数”就是个典型例子给定一个数组要求找出唯一的重复数不能修改数组且只能用常数空间。这道题可以把数组下标和值之间的映射看成一种“隐式链表”从下标0开始当前值作为下一个下标这样数组里的重复数就相当于这个隐式链表的一个环入口。整个解题思路与 141、142 如出一辙。另外判断两个链表是否相交也可以用环形链表的思想先遍历链表 A 到结尾把它的next指向链表 B 的头节点然后对 B 执行环形链表检测如果检测到环说明两个链表原本存在交点环入口就是交点。这个技巧在实际面试中经常出现也说明“判环”能力是一系列难题的共同底座。5.4 常见误区把“有环”和“无限循环”混为一谈最后想说一个概念误区。有环链表是一个数据结构层面的特性程序判断它时不能真的让遍历陷入无限循环而是要设计一个能自动退出且能证明“一定会退出”的算法。这也是为什么哈希表和快慢指针能够成为标准答案而“挨个数数”“转数组”这类思路在极端场景下很难收场。很多人在刷题时会觉得 141 太简单不值得单独复盘。但实际上它融合了链表引用关系、循环不变式、数学推导和复杂度分析是一个很好的“小题目大道理”范本。你如果能在做这道题时主动画出三种解法的空间时间对比再把 142 的入口推导写清楚那么之后的链表题和很多数组题都会顺畅很多。我个人刷完这道题后的体会是不要觉得用哈希表过了就完事试着再想一遍快慢指针最好不看答案手写出来然后在本地跑几个自己造的环把每个指针的位置变化在纸上走一遍。几次下来你就能把一个“入门题”真正内化成自己的基本功。最后分享一个实用小技巧每次刷链表题前在编辑器里先固化为自己常用的链表构造函数再刷环形链表这类题会节省很多重复造数据的时间。