链表题刷到一定阶段876和234这两道题基本都会出现在你的练习列表里而且常常被放在一起。我一开始并没有意识到这一点先刷876时觉得简单两遍遍历就交掉了等做到234立刻卡住——因为要用到找链表中间节点这个技能我却只会先数长度再走一半。于是回过来重新把876用快慢指针写了一遍再回头看234一下就通了。这篇文章会把两题连在一起讲透包括快慢指针为什么可行、中间节点的奇偶边界怎么处理、234题的几种解法各有什么取舍、以及实际编码中特别容易踩的坑。适合刚接触链表的入门者也适合准备面试但想把这组题吃透的人读完你就能自己写出O(1)空间的回文判断。1. 为什么这两道题要放在一起复盘从找中点到判回文的递进关系1.1 876题的本质给链表打个对折链表和数组最大的不同就是没有下标想访问第k个节点只能从头一个一个走。找中间节点的直观办法是先从头到尾走一遍数出长度L再从头走L/2步返回所在节点。这当然能拿到答案但整个链表被扫了两遍。876题真正想让你掌握的是快慢指针这种一次遍历的做法慢指针每次走一步快指针每次走两步快指针到末尾时慢指针刚好停在中间位置。你可以把它想象成两个人绕着操场跑步速度快的跑完全程时速度慢的刚好在半圈位置。道理不复杂但真正写代码时会牵扯出偶数长度返回哪个节点空链表和单节点怎么处理这些边界问题这些正是面试官喜欢追问的点。1.2 234题的隐藏前置技能判断回文链表朴素想法是从两端往中间一步步比较。链表是单向的没法从尾部往前回退所以需要绕一下把后半段链表反转让两个指针分别从头部和中间往后走。这里实际用到了三个技能快慢指针找中点、反转链表、同步遍历比较。你会发现中间节点这一步和876题一模一样。如果876题的快慢指针不熟234题写起来就会卡住反过来876题吃透了234题更像是在此之上叠加一个反转操作的进阶练习。这是两题适合连刷的根本原因前置技能和后置题目咬合得非常紧单独刷任何一题都体会不到这种递进关系。1.3 连刷时的建议顺序和心态我一般建议先刷876把快慢指针写法练到条件反射再刷234在纸上把链表画出来标出奇数和偶数两种长度下快慢指针的轨迹。很多新手只背代码不画图稍微变化就懵。画图这一步看起来慢其实是最快的路径后面遇到环形链表、链表归并排序都会受益。2. 876 的暴力写法与快慢指针的边界推演2.1 为什么暴力解不算真正理解了这道题暴力解可以这样写class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def middleNode_twice(head): length 0 cur head while cur: length 1 cur cur.next steps length // 2 cur head while steps: cur cur.next steps - 1 return cur代码本身没错但问题在于链表被扫了两遍。当链表很长或者说你希望在链表场景下学会用指针的相对位置一次拿到结果暴力的思路就派不上用场了。快慢指针的核心价值是把先量长度再取中点的两趟合并成一趟而且不占用额外空间。2.2 快慢指针的完整推演为什么快指针要走两步先给出最标准的写法def middleNode(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow为什么快指针一次走两步、慢指针走一步因为快指针比慢指针每轮多走一步如果走了t轮快指针走了2t步慢指针走了t步慢指针的路程正好是快指针的一半。快指针停在链表末尾时慢指针自然停在中间附近。换成快指针走3步、慢指针走1步路程比是3:1快指针到末尾时慢指针才走三分之一取不到中点快指针和慢指针同速两个指针永远保持一个身位根本没法感知中点。所以快走2、慢走1是让慢指针恰好落在中点的最简单整数速度组合。再看边界情况。假设链表长度为L奇数长度比如5个节点循环结束时快指针恰好停在最后一个节点上它走过的步数是偶数2t且2t L-1慢指针走了t步停在从头部数第t1个节点正好是正中间的节点。偶数长度比如4个节点循环结束时快指针会走到空指针快指针共走了2t步且2t L慢指针走了t步停在从头部数第t1个节点这个节点是第二个中间节点。876题的要求就是偶数长度时返回第二个中间节点所以这种写法严格匹配题目定义。这也是很多人写题时会忽略的点你以为代码只是找到中间其实它已经隐含了奇偶两种长度的不同落点。2.3 如果题目要求返回第一个中间节点怎么改有些场景需要的是左边中点比如把一个链表拆成两半做归并排序。这时可以用下面这个变体def middleNode_left(head): slow head fast head while fast.next and fast.next.next: slow slow.next fast fast.next.next return slow区别在于循环条件从fast and fast.next变成了fast.next and fast.next.next也就是快指针必须还能安全走两步时才继续。对链表[1,2,3,4]这个写法返回2第一个中间节点对[1,2,3,4,5]返回3正中间节点。这两个写法最好都亲手推一遍面试时被追问为什么别人返回第二个、你返回第一个能讲清楚差异比只会背代码要有说服力得多。3. 234 回文链表的四种思路与空间复杂度取舍3.1 解法一转成数组再判断简单但空间是O(n)最省脑子的做法是遍历一次链表把所有节点值存进数组然后用双指针从两端往中间比def isPalindrome_array(head): vals [] cur head while cur: vals.append(cur.val) cur cur.next left, right 0, len(vals) - 1 while left right: if vals[left] ! vals[right]: return False left 1 right - 1 return True这个写法几乎不会出错也不需要处理链表结构。缺点是空间复杂度O(n)如果链表特别长内存占用会线性增长。如果面试时先用这版面试官基本会追问能不能做到O(1)空间所以它可以作为保底方案但不是最终答案。3.2 解法二找中点反转后半段空间O(1)的标准答案这道题的标准解法是三步用876题的快慢指针找到后半段起点反转后半段链表从头节点和反转后链表的头开始同步比较。Python实现如下def reverseList(head): prev None while head: nxt head.next head.next prev prev head head nxt return prev def isPalindrome(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 reverseList(slow) left head while right: if left.val ! right.val: return False left left.next right right.next return True为什么反转后半段而不是前半段因为前半段从头部到中间的方向本来就是正的可以直接顺序遍历只有后半段的方向反了所以把它原地反转让两个指针分别从两端往中间走。比较时left从头部出发right从反转后的后半段头部出发会经过奇数长度下中间节点的自我比较这个自我比较不影响最终结果。需要注意的是这个写法会修改原链表的结构。如果题目没说不让修改这版就能过如果面试官要求不能修改链表要么改用数组法要么在比较完后再把链表恢复原样恢复方法我放在第4章讲。3.3 解法三递归回溯思路优雅但很可能爆栈链表天然适合递归可以先递归到最后一个节点回溯时让外层指针从头往后同步移动形成从两端夹逼的效果。代码很短但递归深度等于链表长度空间复杂度是O(n)链表很长时会有栈溢出风险。一般不建议作为正解提交更多是用来开拓思路递归的调用栈其实承担了从尾到头的访问能力。3.4 四种思路对比解法时间复杂度空间复杂度是否修改链表主要风险数组双指针O(n)O(n)否空间占用大快慢指针反转O(n)O(1)是需要处理结构恢复递归回溯O(n)O(n)否深度过大可能爆栈快慢指针栈O(n)O(n/2)否需要用额外容器快慢指针栈就是把后半段节点值压入栈再从头比较时逐个弹出思路不难空间是链表长度的一半比数组法略优但仍是O(n)。综合来看快慢指针反转是面试中最值得掌握的方案因为时间最优、空间O(1)还锻炼了原地改链表的能力这在后续的区间反转等题目里都很受用。4. 完整编码与自测从空链表到对称链表的逐项检查4.1 876 题的防御性写法标准写法加上统一的异常处理def middleNode(head): if not head: return None slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow空链表返回None单节点直接返回自身。实际刷题平台给的测试用例通常不会传空链表但自己写单元测试时还是要覆盖。单节点链表进入循环前fast和head都指向唯一的节点因为fast.next为None循环不执行直接返回该节点符合预期。4.2 234 题的完整代码比较之后恢复原链表如果不要求恢复结构第3章的代码就够了。如果要求不修改原链表可以在比较完成后再反转一次后半段并把它接回原来的位置。完整写法如下def isPalindrome_and_restore(head): if not head or not head.next: return True prev_middle None slow head fast head while fast and fast.next: prev_middle slow slow slow.next fast fast.next.next mid slow right reverseList(mid) left head result True cur_right right while cur_right: if left.val ! cur_right.val: result False break left left.next cur_right cur_right.next reverseList(right) if prev_middle: prev_middle.next mid return result关键点在最后两步reverseList(right)把已经反转的后半段再反转回来返回值正好是原来的后半段头节点mid然后prev_middle.next mid把前半段和后半段重新接上。这样原链表完全恢复原样。注意prev_middle是慢指针前一个节点在找中点循环里每次更新最终指向中间节点前一个节点也就是前半段的尾巴。这个修复细节很容易被忽略。我第一次写的时候只想着比较完返回结果后来在同一个进程里继续遍历这个链表做其他操作发现链表结构已经变了才意识到要恢复。面试时主动提出我可以恢复原链表结构通常是个加分项。4.3 必须覆盖的自测用例输入链表876期望输出234期望结果验证点[]NoneTrue空链表[1]1True单节点天然回文[1,2]2False偶数长度返回第二个中间节点[1,1]1第二个True双节点回文[1,2,3]2False奇数长度中间是2[1,2,1]2True奇数长度回文[1,2,2,1]2第二个True典型偶数对称[1,2,3,2,1]3True典型奇数对称[1,2,3,4,5]3False正序与逆序不一致[1,0,1]0True节点值包含0避免比较时出现错误最后一行尤其值得注意链表节点的值可能是0如果你在比较时写if left.val而不是if left.val ! cur_right.val那么当 val 等于0时条件会被当成False判断直接出错。这是一个特别隐蔽的坑因为普通测试用例很难注意到0值节点的特殊性。4.4 实际编码中踩过的坑快慢指针循环条件的顺序。while fast and fast.next里Python会先判断fast是否为None再判断fast.next是否为空这是正确的短路径。如果反过来写while fast.next and fast当fast为None时fast.next直接抛AttributeError。一定要养成先判断自身再判断next的习惯。找中点时对第一个和第二个中间节点混淆。234题使用第二个中间节点作为后半段起点最省心偶数链[1,2,2,1]取第二个2后半段是[2,1]奇数链[1,2,3,2,1]取正中间3后半段是[3,2,1]反转后比较逻辑统一。如果取第一个中间节点奇数长度时比较轮次容易多一轮虽然最终结果往往也是对的但推演起来很容易把自己绕晕。反转后没有恢复链表。这个问题我上面已经演示了恢复代码。记住修改链表结构前先想想要不要保留原结构如果后续还会用到这个链表务必恢复。5. 面试追问与题型延伸快慢指针不止用于找中点5.1 复杂度怎么表达才准确面试官让你分析234题的复杂度标准回答是时间复杂度O(n)空间复杂度O(1)。时间上的O(n)来自快慢指针找中点和最后的同步比较快指针虽然实际访问了约1.5n个节点但常数不影响渐进复杂度所以仍然是O(n)。不要为了显得严谨说遍历了两次快慢指针的本质是两趟遍历合并成了一趟只不过快指针多跑了一段整体的渐进复杂度没有变。5.2 常见追问为什么876题偶数长度返回第二个中间节点因为这是题目定义的。如果你想让代码返回第一个中间节点把循环条件改成while fast.next and fast.next.next也就是快指针能安全跳两步时才继续最终slow停在第一个中间节点。面试官追问时能说出两种写法的差异比直接背答案强得多。5.3 可迁移的题型清单快慢指针不止在这两题里出现下面的题目基本是同一套思路环形链表检测快慢指针同时出发如果相遇说明有环删除链表的倒数第N个节点让快指针先走N步然后快慢同步走快指针到末尾时慢指针正好停在待删节点前对链表做归并排序快慢指针找中点配合合并两个有序链表回文链表变体比如允许删除一个字符再判断是否回文本质仍是双指针加局部验证。更进一步的环形链表 II 还会用到相遇后重置一个指针再走的数学推导但基础还是快慢指针的相对速度概念。我个人在刷这些题时最深的体会是千万不要跳过画图。快慢指针的每一步移动最好在草稿纸上用节点加箭头标出来奇数长度、偶数长度各走一遍。画完之后很多边界条件就不再是死记硬背而是本来就应该这样。我后来做链表归并排序找中点直接复用了第二个中间节点的写法几乎没再出过错。这两道题确实是链表快慢指针的黄金入门组合值得沉下心吃透。