快慢指针找链表中点：两种循环条件的区别与实战

我在面试的时候经常让候选人当场写快慢指针找链表中点。代码短五分钟能写完的人却不多而写完之后能说清楚fast.next and fast.next.next这个循环条件为什么长这样、为什么不能少写一个的人就更是凤毛麟角。大多数人的状态是模板背得滚瓜烂熟但你把条件换成fast and fast.next他就会愣住觉得是不是写错了。其实两个条件都是对的只是它们对应的“中点”语义不一样。这篇文章我想把fast.next和fast.next.next这两个判断逐项拆开讲清楚它们各自在保护什么、停止时快慢指针分别站在哪里、奇数链表和偶数链表的行为差异以及实际工程里这个中点指针拿来干什么用。无论是准备面试还是在项目里写链表拆分、归并排序把这些边界想透了以后遇到各种变体都不慌。1. 快慢指针的核心机制为什么两倍速能精确落在半程先回到最基础的问题链表找中点难点在哪单向链表没有下标每个节点只知道自己的next你不能像数组那样直接arr[n/2]拿中间元素。最朴素的做法是两遍遍历第一遍数出链表长度L第二遍从头走到L/2。这个方案的时间复杂度是 O(n)还挺好理解唯一的问题是你得先完整走一遍才知道总共有多长相当于“回头路”走了两趟。快慢指针的思路则完全不一样。让两个指针同时从头节点出发快指针每次走两步慢指针每次走一步。等到快指针撞到链表末尾或者越过末尾时停下慢指针走过的距离恰好是快指针的一半。快指针走完了整条链慢指针自然就站在半程上。这个道理用一个生活类比特别好懂两辆车同时从起点出发慢车每小时 60 公里快车每小时 120 公里等快车到达终点的那一刻慢车一定在整条路程的正中间。因为快车速度是慢车两倍同一个时间里跑出来的路程也是慢车两倍所以慢车的位置始终是快车位置的二分之一。写成代码就是最常见的骨架slow head fast head while fast and fast.next: slow slow.next fast fast.next.next循环每执行一轮快指针前进两个节点慢指针前进一个节点。链表长度为L时循环执行s轮快指针走了2s步。当2s接近L的时候s自然接近L/2。这就是为什么快指针必须走两步、慢指针必须走一步——两者速度比正好是 2:1才能在一趟遍历之内把中点卡出来。那为什么不像某些题目里那样让快指针走三步、慢指针走一步因为3:1的速度比对应的是“三分之一处”而不是“二分之一处”。快指针到终点时慢指针只走了总长度的三分之一。想找三分点可以这么玩但代码上你要么维护计数器要么用一个辅助指针比next.next这种天然表达“两步”的方式啰嗦得多。next.next正好是两步这就是语言层面给链表找中点开的一扇便利门。这个算法真正的价值在于你不需要事先知道链表长度不需要一个额外的计数器也不需要任何容器存储节点引用。空间复杂度 O(1)时间复杂度 O(n)一趟遍历搞定。理解了这个机制你再看任何“为什么条件长这样”的问题核心就只有一句话循环条件要保证快指针每次跳两步时不会越界或踩空。接下来就是把这个“不越界”翻译成代码。2. 逐一拆解 fast.next 与 fast.next.next非空保护、两步跳转与短路顺序文章标题里这个条件完整的上下文是这种写法slow fast head while fast.next and fast.next.next: slow slow.next fast fast.next.next这和我们上面看到的标准写法只差了一处条件里少了最前面的fast。要搞清楚为什么少了fast反而是安全的就得把两个判断拆开看。2.1 fast.next隐含的“指针非空”检查第一个fast.next字面意思是“快指针的下一个节点存在”。它有两个作用。第一它间接保证了fast本身不为空。在 Python 这类语言里访问null.next会直接抛异常。而fast.next这个表达式能被安全求值前提就是fast不是空节点。所以你写fast.next实际上已经把“fast 非空”这一层检查一起带上了。这就是为什么标题里的写法不需要单独再写一个fast and开头——只要fast.next能成立fast肯定还站在某个真实节点上。第二它同时说明“快指针至少还能再走一步”。如果fast.next是None说明快指针已经站在链表最后一个节点上它往前走一步就会越界循环无论如何都得停。2.2 fast.next.next为两步跳转做最终确认再看第二个fast.next.next。这个判断才是真正决定“快指针能不能走两步”的检查。在循环体里快指针执行的是fast fast.next.next意思是一口气跳到后面第二个节点上。这个操作要想合法不仅要求fast.next存在还必须要求fast.next.next也存在。如果fast.next不为空但fast.next.next是None说明快指针前面只剩一个节点走一步可以走两步就会踩出链表边界。所以这两个判断合在一起就是在说一句话快指针有路可走而且还有足够长的路能撑住它跳两步。这种模式其实在日常生活中也常见。过马路要等两个方向都没车才走fast.next是“第一条车道没车”fast.next.next是“第二条车道也没车”两个都满足才能执行fast fast.next.next这个跨越动作。2.3 短路求值顺序天然空指针安全还有一个很关键的细节藏在语言的求值顺序里。and是从左到右的短路运算符左边为假时右边根本不会执行。while fast.next and fast.next.next这个顺序设计得非常讲究。执行到fast.next.next时Python 已经确定fast.next不为空所以访问它肯定安全。也就是说第一个判断先帮第二个判断探了雷第二个判断才能放心大胆地读。如果把顺序反过来写成while fast.next.next and fast.next逻辑上看着好像还是那三个变量但真跑起来第一个循环就可能炸。因为当fast.next是None时fast.next.next这一步就已经在空指针上操作了后面的and fast.next根本没机会执行。这也是我在实际 code review 里见过最多的问题之一后面第 5 章我会专门再提。2.4 循环停止时指针们站在哪明白了两个判断的职责再看循环结束的时刻。写法while fast.next and fast.next.next停下时只可能有两种情况fast.next为None快指针已经到了最后一个节点前方无路可走。fast.next.next为None快指针站在倒数第二个节点上它只能再走一步走两步就会越界。不管哪种此刻快指针都已经走完了它能安全走完的最远距离最多也就差一步。而慢指针只走了快指针一半的步数也就是“能安全步数的中点”。这个停止位置就是你要的那个中点指针只不过在偶数长度链表里它到底是左边还是右边那个中间节点还得细看也就是下一章的问题。3. 偶数链表的中点选择不同写法背后的语义差异很多人背模板时忽略了一个事实“中点”这个词在偶数长度的链表里本身是有歧义的。一个长度为 4 的链表节点依次是 1、2、3、4中间位置到底算 2 还是 3两者都对取决于你需要哪种语义。如果你用的是最常见的while fast and fast.next走一遍看结果链表 1 - 2 - 3 - 4 - None初始slow1, fast1fast非空fast.next2非空进入循环slow2, fast3fast非空fast.next4非空进入循环slow3, fastNonefast为空循环退出最后 slow 停在 3。也就是说标准写法在偶数长度时返回的是靠右的那一个中间节点代码社区里一般叫“后驱中点”。而标题里的写法while fast.next and fast.next.next同样是 1 - 2 - 3 - 4 - None初始slow1, fast1fast.next2非空fast.next.next3非空进入循环slow2, fast3fast.next4非空fast.next.nextNone条件不满足循环退出slow 停在 2。偶数长度时返回的是靠左的那一个中间节点也就是“前驱中点”。同样找中点两种写法差了整整一个节点位置。这个差异我整理成一张表方便对照链表长度节点序列while fast and fast.next结果while fast.next and fast.next.next结果1[1]1空指针异常需前置处理2[1, 2]213[1, 2, 3]224[1, 2, 3, 4]325[1, 2, 3, 4, 5]33看出规律了吗奇数长度时两种写法完全一样因为奇数链表只有一个唯一的中间节点。偶数长度时才会分道扬镳一种取右边的一种取左边的。为什么 LeetCode 876 这类题目的官方题解常用while fast and fast.next因为题目里明确定义了有中间节点并列时返回第二个中间节点。而如果你做的是链表归并排序、按中点切分链表这类操作很多时候你希望拿到的是一半偏左的节点这样才能保证切出来的左右两段长度尽量均匀左侧不会比右侧多出两个节点。这时while fast.next and fast.next.next就更合适。还有一个衍生写法也值得记住如果你希望快慢指针起点相差一位让慢指针天然偏左可以把慢指针初始化为head、快指针初始化为head.next再配合while fast and fast.next循环。这样在长度为 2 时slow 停在 1也得到前驱中点。本质和标题里的写法是同一件事只是用初始化位置替代了条件判断。所以不要问“哪个写法是对的”要问“你现在需要的中间节点是哪一个”。4. 中点指针的三种实战场景拆分、回文判断与归并排序快慢指针找中点本身不是终点它只是给后面操作提供了一个可靠的锚点。我做项目里用到它最多的是三个场景。4.1 按中点拆分链表这是链表归并排序和部分分治算法的基础操作。拿到中点之后你要把链表切断成左右两条独立链表。关键在于切断前先把右半段的头指针存下来否则一断开就找不回来了。常规写法长这样def split_linked_list(head): if not head or not head.next: return head, None slow head fast head.next # 快指针先走一步让 slow 最终落在左半段末尾 while fast and fast.next: slow slow.next fast fast.next.next right_head slow.next slow.next None # 切断左半段和右半段 return head, right_head这里有个细节快指针被初始化为head.next而不是head。这样一来偶数长度链表里 slow 会稳稳停在左半段的最后一个节点上。比如 1 - 2 - 3 - 4最终 slow 停在 2右半段从 3 开始左半段 1 - 2两边长度正好相等。如果这里用标准写法slow 会停在 3右半段只有 4 一个节点左半段却有 3 个节点长度差被放大递归排序的分治效果就差一些。4.2 回文链表判断判断一个链表是否回文经典做法是三步找中点、反转后半段、逐节点比较。这里的中点选择也有讲究。def is_palindrome(head): if not head or not head.next: return True slow head fast head while fast and fast.next: slow slow.next fast fast.next.next right_head reverse(slow) # 反转后半段 left head right right_head while right: if left.val ! right.val: return False left left.next right right.next return True回文判断里我推荐标准的while fast and fast.next也就是返回靠右的中点。因为反转后半段的时候如果中点选得偏左右半段会比左半段长比较循环就得额外处理指针越界选偏右的中点右半段最多跟左半段一样长以右半段为循环条件非常安全。奇数长度时中间那个节点会被反转后的自己跟自己比较一次不影响结果。4.3 链表归并排序归并排序对链表特别不友好因为链表不支持随机访问没法像数组那样一挥手从中间劈开。这时候快慢指针找中点几乎是唯一灵活的切分手段。递归函数里先找到中点把链表切成两半对两半分别排序再写一个合并两个有序链表的函数把它们合起来。与 4.1 一样这里通常也选择前驱中点。原因很简单切分出来的两个子链表长度越接近递归深度越均衡排序效率越稳定。用后驱中点虽然也能跑但每次左侧都比右侧长极端情况下递归树的平衡性会变差。这三个场景的共通点其实都是先找一个可靠的锚点再围绕锚点做切断或者对称比较。快慢指针的价值不在于“找到中点”这个动作本身而在于它为后面这些复杂操作提供了一个不需要预知长度就能得到的稳定基准。5. 实际编码中容易踩的坑条件顺序、空指针与引用丢失光把原理弄通还不够手写代码时真正耽误时间的往往是几个不起眼的坑。我一个个说。5.1 条件顺序写反更早踩雷有同事为了省事把条件写成这样while fast.next.next and fast.next:看起来只是把两个判断调换了位置逻辑上“都是判断那三个变量非空”对吗不对。链表只有两个节点的时候第一次进循环fast.next存在但fast.next.next是None。None是个假值按说循环不该进去但因为and左求值先看fast.next.next在你判断它是假值之前这个表达式本身已经完成了“读取None.next”这个动作直接抛异常。所以条件顺序不是排版问题是执行顺序问题。把更基础的检查放前面永远是好习惯。5.2 空链表和单节点的前置处理标题里的写法尤其要在入口做好防护。空链表时head是Nonehead.next直接崩溃单节点时head.next是Nonehead.next.next同样崩溃。我习惯在最前面加一层if not head or not head.next: return head这样空链表、单节点都被拦下来后面的快慢指针逻辑只需要考虑节点数大于等于 2 的情况。别小看这一行它同时也是很多面试题目的第一个边界考察点。5.3 切断链表时丢了右半段头指针拆分链表时如果先执行slow.next None再想取右半段头指针就已经晚了。因为slow.next已经被置空你永远拿不到原来的后续节点。正确顺序是先存后断right_head slow.next slow.next None这个顺序错误在真实工程里更容易发生因为大家都记得要断开却忘了断开之前先把“未来的头”攥在手里。5.4 盲目改写成 for 循环有人觉得 while 循环太朴素想用固定次数的 for 循环来模拟快指针走两步。这很容易翻车因为你无法在不知道链表长度的情况下确定循环次数。for 循环要么剩余次数太多导致快指针越界要么次数不够导致慢指针还没走到中点。这类问题天生适合 while因为循环次数由“指针能不能继续安全前进”这个条件动态决定而不是由预先算好的数字决定。5.5 快速验证方法画一个四节点链表我不止一次在工位上跟人讲边界问题讲半天不如直接在纸上画一个 4 节点链表手动走两遍循环把每次 slow 和 fast 的位置写下来。一轮下来条件选择带来的差异就全清楚了。这个方法也适用于你自己写完代码后的自查。写一个简单的辅助函数把数组转成链表再用不同的数组长度跑一遍打印每一轮 slow 和 fast 指向的值往往几秒钟就能定位问题def array_to_linked_list(arr): dummy ListNode(0) cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next配合一小段遍历打印代码边界行为一目了然。我自己现在的习惯是拿到这种题先不急着写循环先问自己一句“循环结束时快指针应该站在哪个位置”。把停止状态想清楚条件自然就写出来了。fast.next and fast.next.next看着绕其实无非是在说“快指针还能再安全地跳两步”。以后你看到while fast and fast.next或者把快指针初始化为head.next的变体都能第一时间反应过来它们对应的中点语义是什么。画一个四节点链表手工推两遍比背任何模板都可靠。