快慢指针找链表中点：为什么循环条件要写fast.next.next

1. 先从“为什么找中点还要分奇偶”说起在面试和实际开发中链表题是最容易出边界问题的题型之一。快慢指针找链表中点这道题几乎每届面试都会遇到但每次讲原理的时候总会有同学追着问一句为什么循环条件要写成fast.next and fast.next.next写成fast and fast.next不行吗我第一次被问到这个问题的时候也愣了一下。当时我脑子里只有一套“快指针走两步、慢指针走一步”的模糊印象真被追问到边界条件时才发现自己其实没有把这个算法彻底想透。先说结论这个条件不是“唯一写法”但它是“最稳写法”。它直接决定了偶数长度链表返回的是上中点还是下中点也决定了循环体里fast fast.next.next会不会在某一步撞上空指针。更关键的是这个问题不是链表题的特例你如果把它换到数组有序去重、寻找重复数、链表判环这些场景会发现快慢指针的边界条件处处都是坑。这篇文章不打算给你抄一段代码就走而是把“为什么”这一层彻底掰开。你看完之后不仅会写这套算法还能自己推导出为什么要有fast.next.next这个检查以及在不同题目里应该怎么调整条件。1.1 用跑步来理解快慢指针的核心直觉想象你和朋友在一条跑道上跑步你的速度是他的两倍。他跑了1圈的时候你跑了2圈。如果跑道不是封闭的是一条直线你从起点跑到终点时他只跑了一半路程。这一半的位置就是这条跑道的“中点”。链表找中点的思路一模一样。慢指针slow从头节点开始每次移动1步快指针fast每次移动2步。当fast走到链表末尾时slow恰好停在中间位置。这个思路本身不复杂复杂的是“当快指针走到末尾”这句描述在代码里怎么表达。因为链表的末尾有两种情况链表长度是奇数时fast停在最后一个节点链表长度是偶数时fast会越过末尾停在null上。这两种情况对应的循环条件不同最终返回的“中点”定义也不同。要理解标题里的问题必须先理解这个奇偶差异。1.2 上中点与下中点很多教程没有说透的概念对于长度为偶数的链表比如1 - 2 - 3 - 4中点到底该返回2还是3严格来说这条链表的中间有两个候选节点许多算法题中会根据你的循环条件不同返回“上中点”或“下中点”。上中点中间位置偏左的那个也就是第n/2个节点。下中点中间位置偏右的那个也就是第n/2 1个节点。leetcode上的很多题目其实对“中点”的期望结果是有明确规定的但在初学阶段很多人根本没意识到自己写出的版本是上中点还是下中点。这个差异一旦没搞清后面做回文链表判断、链表排序时就会莫名其妙地出错。2. 循环条件逐行拆解三种写法到底差在哪现在直接进入正题。找中点最常见的三种循环条件写法是# 写法A只判断快指针本身 while fast: ... # 写法B判断快指针和下一位 while fast and fast.next: ... # 写法C判断快指针、下一位和下下位 while fast and fast.next and fast.next.next: ...标题里问的fast.next and fast.next.next就是从写法C变形来的。在fast不为空的前提下这个条件可以简写为fast.next and fast.next.next但完整的标准写法永远是带fast判断的。为什么要把这三种写法单独拎出来说因为它们在偶数长度链表上的行为完全不同而且其中写法A在某些情况下会产生死循环或空指针异常。2.1 写法A的崩溃现场为什么不能只用 fast先用一个空链表的情况来看fast指向nullwhile fast直接不进入循环返回slow也就是null。这里没问题。再看链表只有两个节点1 - 2。初始时fast 1进入循环体后执行slow slow.next此时slow变为2。fast fast.next.next也就是2.next即null。循环条件再次检查fast null退出循环。最终返回slow 2对于1 - 2这条链表来说返回的是第二个节点。奇怪这里并没有报错返回的节点也不算离谱。问题出在哪问题出在链表长度为更长的偶数时比如1 - 2 - 3 - 4初始fast1slow1。第一次循环后slow2fast3。第二次循环后slow3fastnull。退出循环返回slow3。返回3也就是下中点。可如果你心里期望的是上中点2那这里就直接错了。更严重的问题出现在长度更长的链表上吗其实并不会空指针因为写法A在fast为null时就退出了不会去访问fast.next。但写法A有个致命问题在循环体内执行fast fast.next.next时如果此时fast.next已经为null那么fast.next.next就会尝试访问null.next直接抛出空指针异常。我用一个具体例子证明链表1 - 2 - 3。初始fast1slow1。第一次循环fast1fast.next2不为空进入循环体执行fast fast.next.next 3slow2。第二次循环检查fast3不为空进入循环体执行fast fast.next.next但3.next是null那null.next就报错了。看到没有写法A在链表长度为3时就会崩。原因就是在进入循环体之前没有检查fast.next是否为null一旦快指针在倒数第二个节点上fast.next.next就会越界。2.2 写法B的真实行为能跑但返回的是下中点while fast and fast.next是最多初学者写出的版本因为它看起来很安全fast和fast.next都不为空那fast.next.next总该安全了吧不好意思这个逻辑有个陷阱。while fast and fast.next只能保证在条件检查的那一刻fast和fast.next都不为空。但进入循环体后你执行的是fast fast.next.next这一行代码在赋值之前需要对fast.next.next取值。如果fast已经移动到最后一个节点那么fast.next就是null此时fast.next.next就是null.next。我们还是用链表1 - 2 - 3验证第一次循环前fast1fast.next2条件成立。循环体内slow2fast fast.next.next 3。第二次循环前fast3fast.nextnull条件不成立退出循环。这里并没有报错因为条件检查终止了循环。最终返回slow2对于长度为3的链表来说结果是正确的。再看链表1 - 2 - 3 - 4第一次循环前fast1fast.next2条件成立。循环体内slow2fast fast.next.next 3。第二次循环前fast3fast.next4条件成立。循环体内slow3fast fast.next.next null。第三次循环前fastnull条件不成立退出循环。最终返回slow3不是我们可能期望的2。所以写法B能跑但返回的是下中点。如果你在做回文链表判断时需要从中间断开拿到下中点去做反转也是可以的关键是你要清楚自己在写的是哪个中点。2.3 写法C的本质提前挡住越界顺便把中点定义变回上中点现在看正解while fast and fast.next and fast.next.next: slow slow.next fast fast.next.next这行代码在进入循环体之前额外检查了fast.next.next是否为null。这有什么好处看链表1 - 2 - 3 - 4第一次循环前fast1fast.next2fast.next.next3条件成立。循环体内slow2fast3。第二次循环前fast3fast.next4fast.next.nextnull条件不成立退出循环。最终返回slow2。注意同样是长度为4的链表写法B返回3写法C返回2。这正是上中点与下中点的区别。再看链表1 - 2 - 3第一次循环前fast1fast.next2fast.next.next3条件成立。循环体内slow2fast3。第二次循环前fast3fast.nextnull条件不成立退出循环。最终返回slow2正确。再看链表1 - 2第一次循环前fast1fast.next2fast.next.nextnull条件不成立直接退出。最终返回slow1。对于长度为2的链表上中点是1返回1完全符合预期。写法C之所以安全是因为它把“进入循环体”的门槛抬高到了“下一步还能再走两步”的程度。它确保了循环体内执行的fast fast.next.next不会访问到null.next同时让快指针在链表长度为偶数时停在倒数第二个节点而不是越过末尾从而让慢指针精确停在所有节点中的“前半段中间位置”。2.4 三种写法对比速查表链表长度写法Awhile fast写法Bwhile fast and fast.next写法Cwhile fast and fast.next and fast.next.next0nullnullnull1节点1节点1节点12节点2节点2节点13空指针崩溃节点2节点24节点3节点3节点25空指针崩溃节点3节点3从这个表能直观看出来写法A在奇数长度链表上存在空指针崩溃风险写法B在偶数长度时返回下中点写法C在偶数长度时返回上中点。回到标题的问题为什么要写fast.next and fast.next.next因为很多时候你想要的“中点”默认是上中点而且这个写法在循环体内不会触发空指针一次把两个坑都填平了。3. 从找到中点到解决真实问题这套思想能延伸多远搞清楚了循环条件之后别急着看下一题。快慢指针的价值远不止“找中点”这一件事它在链表相关的多个场景里都是核心套路而且它们的“边界条件”处理思路完全一致。3.1 链表判环同样的“会不会越界”问题链表中判断是否有环最经典的写法就是Floyd判圈算法两个指针一快一慢如果有环快指针最终会从后面追上慢指针。这个算法的循环条件一般是while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True你注意判环用的是写法B而不是写法C。为什么不统一用写法C因为判环这个场景下链表末尾并不存在“上中点还是下中点”的选择问题。快指针在空链表或单节点链表上会直接退出在有环链表上则会无限循环直到相遇。边界定义变清晰了循环条件也就不需要多加一层fast.next.next的判断。这个对比非常有意思同一个“速度差”模型在不同的题目里循环条件居然要跟着变化。这提醒我们背模板不能只背一行代码要理解每个条件在为什么服务。3.2 有序数组原地去重快慢指针思想换个容器一样能打热搜词里有“js快慢指针有序数组原地去重”这是快慢指针从链表迁移到数组的经典案例。题目要求在不使用额外数组空间的前提下把有序数组中的重复元素去掉。思路是用一个慢指针表示“当前已去重数组的末尾”用一个快指针遍历整个数组。当快指针指向的元素和慢指针指向的元素不同时把快指针的值复制到慢指针后面一位。这个过程本质上是“保留不重复的元素跳过重复的元素”。function removeDuplicates(nums) { if (nums.length 0) return 0; let slow 0; for (let fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }这段代码不需要fast.next这种判断因为数组天然支持随机访问fast永远不会越界。但核心思想依然是“一个指针探测前方另一个指针记录结果位置”。理解了这个思想你会发现在处理“原地操作”类题目时快慢指针几乎是第一反应。3.3 寻找倒数第k个节点换个起点同样的双指针节奏快慢指针还能用来找链表的倒数第k个节点。思路是让快指针先走k步然后快慢指针同步前进。当快指针到达末尾时慢指针正好指向倒数第k个节点。这里对循环条件的要求和“找中点”不同因为你有两个阶段第一阶段快指针先走k步第二阶段两个指针一起走。如果k等于链表长度快指针第一次走完后正好是null第二阶段直接不进入循环此时慢指针恰好在头节点也就是倒数第k个节点。这种灵活性恰恰是快慢指针的魅力所在。你不需要记住每种题目的模板只需要理解“谁先走、走多快、什么时候停”这三个变量就能自己推导出正确的代码。3.4 回文链表判断找中点只是开胃菜很多链表面试题其实是由多个基础操作组合而成的回文链表就是典型例子。判断一个链表是否为回文结构最标准的做法分三步用快慢指针找到链表的中点通常用上中点或下中点看你的反转策略。把后半部分链表原地反转。用两个指针从头部和中部同时遍历比较每个节点的值。这里快慢指针找的“中点”决定了你在反转后半部分时从哪里断开。如果你找的是上中点那么当链表长度为偶数时后半部分从slow.next开始反转如果你找的是下中点那slow.next的位置又不一样了。边界差一位整个反转逻辑全乱。这就是为什么我总强调要搞清楚“上中点”和“下中点”的区别。很多人在这一步不重视写完了发现测试用例过了提交之后偶数的 case 就是不对问题就出在这个“中点的定义”上。4. 实际操作中的细节从节点结构到空指针防御前面的分析都是理论层面的真正写代码的时候还有一些看似不起眼、实际上能坑死人的细节。4.1 节点结构定义语言差异带来的边界处理差异在C/C里链表节点的结构体定义通常是struct ListNode { int val; struct ListNode *next; };C语言中操作节点时最常见的崩溃原因就是解引用了空指针。用快慢指针找中点时哪怕你写了while fast fast.next fast.next.next也要小心slow slow.next这一步。在某些极端情况下比如链表长度为1时slow.next本身就是null如果把slow移动到null后面再访问slow.val就崩了。C的nullptr和 C 的NULL本质上是同一类问题只是编译期会给你一些警告。Java 里所有引用类型默认是nullPython 里是NoneJavaScript 里是null或undefined。不同语言对空指针的报错信息不一样但核心防御思路一致在任何-next或.next之前先确认当前节点不是空。Python 里没有指针语法但None的next访问同样会抛AttributeError。很多人在刷题平台上用 Python 写链表题觉得“Python 没有指针应该不会空指针吧”其实NoneType的next访问照样炸。4.2 实操步骤从零到一写出可用的找中点函数我自己常用的找中点模板是这样的def find_middle(head): if head is None: return None slow head fast head while fast and fast.next and fast.next.next: slow slow.next fast fast.next.next return slow这个函数返回的是上中点。如果你需要下中点把slow的初始位置改到head.next是不对的正确做法是调整循环条件或者再往前提一次。# 返回下中点的写法 def find_middle_lower(head): if head is None or head.next is None: return head slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow注意这个写法在处理长度为2的链表时slow会移动到第二个节点返回的是下中点。在长度为3时fast在第二次循环时停在最后一个节点然后退出slow移动一次到第二个节点仍然是下中点和上中点重合的位置。所以如果你看到网上的题解里有“先快慢指针找中点然后slow.next作为后半部分起点”的写法那么它用的可能是上中点如果看到另一种写法“直接找中点后从slow开始处理”那可能是下中点。两者没有绝对的对错关键是你自己心里要有一杆秤。4.3 边界情况清单动手之前先扫一遍这四种输入我总结了一份“找中点前必查清单”每次写代码之前或写完代码之后我都会按这个清单自查一遍空链表head null函数应该返回null不能抛异常。单节点链表head.next null返回头节点本身。双节点链表如果求上中点返回第一个节点求下中点返回第二个节点。偶数长度链表确认你的循环条件返回的是上中点还是下中点并且在注释里写明。很多初学者写完代码后只测了奇数长度和偶数长度各一个用例就以为自己写对了。但真正容易出错的其实是“单节点”和“双节点”这两个极端因为它们会让fast.next.next的判断直接短路如果短路逻辑没写对循环条件直接退出结果就会很怪。4.4 调试技巧把指针挪动过程画出来链表的调试比数组难因为你看不到指针的移动轨迹。我自己调试快慢指针相关代码时有一个土办法特别管用在循环体里加两行打印把每一轮slow和fast的指向打出来。while fast and fast.next and fast.next.next: slow slow.next fast fast.next.next print(fslow - {slow.val}, fast - {fast.val})这段打印能让你直观地看到每一步两个指针的位置尤其是循环退出前的那一步最容易暴露“快指针为什么停在这里”的真相。在 LeetCode 这种在线评测平台上print是可以用的不会影响提交结果。在笔试环境里如果没限制输出也可以用这个方法快速自查。5. 典型场景实录一个真实的“中点引发的血案”我印象很深的一次在线笔试题目是“判断一个链表是否为回文链表”。候选人写得很顺思路完全正确快慢指针找中点反转后半部分逐个比较。但他用的是while fast and fast.next这种写法返回的是下中点。反转后半部分时他直接从slow.next开始反转结果整个后半部分少了一个节点。最后跑奇数长度用例是好的跑偶数长度用例就对不上。那次笔试结束后他来找我复盘我让他把循环条件改成while fast and fast.next and fast.next.next所有用例直接通过。这件事给我的启发是快慢指针找中点真的不是“背一个循环条件就完事”它直接决定了你后续所有逻辑的起点。起点差一位后续差千里。5.1 常见问题速查表现象可能原因解决方案空链表时返回异常没有判空函数开头先判断head是否为null偶数链表返回右边节点使用了while fast and fast.next改成while fast and fast.next and fast.next.next奇数链表空指针异常循环条件没有判断fast.next采用完整条件fast and fast.next and fast.next.next死循环快指针移动逻辑写错比如fast fast.next检查步长是否为2返回的“中点”位置与题设不符上中点/下中点理解混淆对照本表第2行确认循环条件5.2 快慢指针的另一个经典坑链表判环的相遇节点找中点和判环是快慢指针的两个核心应用但很多人在判环时会遇到一个现象快慢指针相遇了相遇点却不一定是环的入口。这个问题的解法需要再引入一个指针从头节点出发和相遇点指针逐步前进最终在环入口相遇。这个推导过程在经典的 Floyd 算法里有严格的数学证明核心结论是快慢指针相遇时慢指针走了 k 步此时从链表头部到环入口的距离和从相遇点到环入口的距离相等。所以把其中一个指针拉回头节点两个指针每次各走一步第一次相遇的位置就是环入口。这个扩展说明一个问题快慢指针只是工具真正的高手拿到工具之后会去思考推导过程而不是只会套模板。5.3 性能与复杂度为什么没人用“先数个数再走一半”有人会问找链表中点不是可以先遍历一遍数出链表长度再从头走到一半位置吗这样做结果一样干嘛要快慢指针答案是一个“空间换时间”之外的问题时间复杂度。先数个数再走一半需要两趟遍历第一趟数个数第二趟走一半总共会遍历 1.5n 个节点。快慢指针只需要一趟遍历快指针走 n 步的同时慢指针走过 n/2 步总共也是 n 步。相比下来快慢指针几乎省掉了“额外半趟”的开销。更重要的是在一些只需要“一趟遍历”约束的题目里快慢指针是唯一满足要求的方案。比如长度未知的单向链表你不能先缓存长度再回头走因为单向链表无法回头除非你用数组把所有节点存下来但那引入了 O(n) 的额外空间。快慢指针用 O(1) 空间就实现了一趟扫描定位这就是它的价值。6. 写在最后这个条件背后的思维方式如果你读完这篇文章只记住一件事我希望你记住的是fast.next and fast.next.next不是死背下来的咒语它是对“快指针还能不能安全地走两步”这一问题的回答。写链表相关代码时最重要的思维方式是“假设你已经站在某个节点上下一步还能不能走”这个“下一步还能不能走”的判断比任何模板都重要。我的习惯是拿到链表题先画一个小规模的链表长度为1、2、3、4各画一遍走一下循环看指针落在哪里。这样走完四遍循环条件自然就有了不需要背。快慢指针这个套路从找中点、判环、找倒数第k个节点到有序数组原地去重本质都是一回事两个指针不同速度各自维护一个意义。你把“谁快谁慢、谁先走、谁停下”这三个问题想清楚任何变体都能顺手解出来。希望这篇笔记能帮你在下次遇到链表题时少走一次“为什么我的偶数用例又挂了”的弯路。