刷 LeetCode 的人应该都绕不开 234 这道题。题号 234名字叫回文链表在“热门 100 题”里属于那种看着简单、一写就出问题的小坎。很多人第一次做它的时候会想回文不就是正着读和倒着读一样吗那我把它转成数组再两头比不就完了对这是能 AC 的思路但如果你只是这么写完就翻篇那这道题等于白做。回文链表考的不只是“判断回文”这个动作更考验你对链表指针操作、原地反转、边界处理的基本功。这篇文章我想把这个题从题目到解法到面试追问全部拆开讲一遍尤其是那个“快慢指针找中点 反转后半段”的标准最优解我会把每一步为什么要这么做、坑在哪里都说明白让你不仅能写出代码还能在面试时把思路讲得清清楚楚。1. 题目到底在考什么回文链表的本质与考点拆解1.1 先读懂题目链表回文的判断标准题目要求很简单给你一个单链表的头节点head判断它是不是回文链表。回文的定义就是正着读和倒着读都一样比如1 - 2 - 2 - 1就是回文而1 - 2 - 3 - 2 - 1也是回文但1 - 2 - 3就不是。但注意链表和数组不一样数组可以通过下标随机访问链表只能从头到尾一个一个往下走。所以“正着读和倒着读”这件事在链表里没有那么直观。你要判断回文本质上需要把前半段和后半段做比较而难点就在于链表不给你“倒着读”的能力你必须想别的办法拿到后半段的逆序状态。这道题给的约束也值得看一眼链表节点数在[1, 10^5]之间节点值是一个 32 位整数。10 万这个量级意味着O(n)时间、O(n)空间是可以接受的但并不是最优的。如果你在面试中直接写出一个开数组的解法面试官大概率会追问一句“能不能不用额外空间”这就是这道题真正的分水岭。1.2 这道题为什么会出现在热门 100 题里回文链表能进热门 100 题不是因为它难而是因为它太典型了。它同时踩中了链表题里几个最常考的知识点寻找链表中间节点、反转链表、双指针思想。这三个技能几乎是链表类算法题的“地基”而回文链表恰好把这三个地基动作串在一起。你去看 LeetCode 周赛和面试题链表题翻来覆去就是那几板斧删除倒数第 N 个节点要用快慢指针环形链表要用快慢指针反转链表 II 要处理局部反转合并两个有序链表要会 dummy 节点。回文链表这道题如果你能独立写出空间O(1)的解法那说明你对“快慢指针”和“反转链表”这两个技能已经形成了肌肉记忆。反过来如果你连这道题都还需要看题解才能过那后面遇到更复杂的链表题会更吃力。所以我的建议是这道题不要满足于“AC 了就行”至少要把三种解法都写一遍理解它们各自的取舍这样才算真正把这道题吃透。2. 解法一把链表变成数组用双指针扫2.1 思路与实现最容易想到的思路是先遍历一遍链表把每个节点的值按顺序存到一个数组里然后对标数组的首尾双指针一个从左边走一个从右边走只要发现不相等就返回 false。遍历完整个流程如果都没冲突就说明是回文。这个思路的好处是清晰、不容易出错特别适合作为面试时的“保底方案”。你可以在 3 分钟之内写完并且保证正确然后再说“我知道有更省空间的解法”这样至少不会在写不出最优解的情况下交白卷。代码也不复杂我用 Python 写出来长这样class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: 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这里唯一的注意点是链表可能为空或者只有一个节点。不过本题的约束已经说了节点数大于等于 1所以不用特判空链表。但如果你在本地测试或面试手写还是可以习惯性加一句if not head or not head.next: return True这样更稳妥。2.2 复杂度与适用场景这个解法的时间复杂度是O(n)空间复杂度也是O(n)因为你需要一个和链表一样长的数组来存值。在 LeetCode 上跑 10 万级别的数据没有任何压力运行时间通常能进前一半。那它的问题在哪问题就在空间。面试官喜欢问的是“你能把空间复杂度降到O(1)吗”。如果你的回答是“可以”但写不出来这就比一开始就说“我只能想到数组法”还要糟糕。所以我的建议是数组法当作热身和兜底但绝不能只停在这一层。另外要补充一点如果你用 C 或 Java数组可以用vectorint或ListIntegerPython 直接 append 即可。判断回文时也可以只比较到中点前半部分和后半部分对折比较没必要遍历到末尾。不过双指针自然是到left right时停止所以“比较到中点”已经隐含在里面了。3. 解法二快慢指针找中点 反转后半段最优解3.1 为什么需要找中点和反转既然要空间O(1)那就不能开额外数组。剩下能用的只有链表结构本身。思路核心是回文链表的前半段和后半段是镜像对称的那么如果我能把后半段原地反转再和前半段逐节点比较就能判断是否回文。但反转整个链表不行因为那会把链表的顺序完全颠倒和前半段对不上。我需要做的是先找到链表的中间节点然后把中间节点之后的链表反转最后用两个指针同时遍历前半段和反转后的后半段逐个比较值。这里有个关键点找到中间节点之后链表被分成了两截。原来的前半段仍然保持原来的顺序后半段被反转成逆序。比如链表1 - 2 - 3 - 2 - 1中间节点是3后半段是2 - 1反转后变成1 - 2。此时用p1指向1p2指向反转后的1比较1 1然后p1到2p2到2相等最后结束返回 true。整个过程中没有用到额外数组。3.2 手把手拆解每一步我把完整代码先放在下面再逐步解释class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: if not head or not head.next: return True # 第一步快慢指针找中点 slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next # 此时 slow 指向中间节点或中间偏右 # 第二步反转从 slow 开始的链表 prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt # 第三步比较前半段和反转后的后半段 left, right head, prev while right: if left.val ! right.val: return False left left.next right right.next return True第一步“快慢指针找中点”slow每次走一步fast每次走两步。当fast走到链表尾部时slow正好停在中间位置。如果是奇数个节点slow指向正中间那个节点如果是偶数个节点slow指向中间偏右的那个节点。这个偏右是刻意为之的比如1 - 2 - 2 - 1节点数 4slow最终指向第二个2。此时反转从第二个2开始的子链表得到1 - 2和前半段1 - 2正好对应。第二步“反转后半段”把slow作为反转的起点用标准的三指针迭代反转法让cur从头往后移动同时把每个节点的next指针翻转指向前一个节点。反转结束后prev指向的是反转后的后半段链表的头节点。第三步“逐节点比较”left从原始head出发right从反转后的后半段头节点出发。循环条件用while right因为后半段一定不比前半段长。如果中间有不相等的值直接返回 false走到right为空说明后半段全部比较完且都相等返回 true。3.3 边界条件与细节坑这个解法最容易踩的坑有三个。第一个坑是“找中点时fast和fast.next的判断顺序”。如果你写成while fast.next and fast那么当fast为空时你先去访问fast.next就会抛空指针。正确顺序一定是先判断fast本身不为空再判断fast.next不为空。写成while fast and fast.next才是对的。第二个坑是“反转后半段后原始链表的结构被破坏了”。严格来说这个解法在比较完之后没有把链表恢复到原来的样子。如果你只是在 LeetCode 上做题这不影响 AC因为判题只检查返回值。但如果是在面试现场面试官可能会问“你的函数会不会改变原链表”这时候你可以说“会后续如果需要恢复可以再把后半段反转回去”。有的面试官会要求你不修改原链表那你可以采用另一种处理方式找到中点后把前半段反转然后比较前半段和后半段这样不需要修改后半段的结构。但更常见的做法是反转后半段并在比较结束后把链表恢复原状这算是一个加分项。第三个坑是“偶数长度和奇数长度的比较结束条件”。我用while right作为循环条件这样在奇数长度时比如1 - 2 - 3 - 2 - 1反转后的后半段是1 - 2right只有两个节点比较到right为空时自然结束中间节点3不需要参与比较因为它和自身对称不影响结果。在偶数长度时right的长度和前半段一样同样能正确比较。如果你用while left and right作为条件也能正确但用while right更少一次判断。还有一个细节当链表长度为 2 时比如1 - 2slow会指向第二个节点2反转后半段后prev指向2left是1right是2比较时发现1 ! 2返回 false。符合预期。4. 解法三递归与栈的思路对比4.1 递归实现与原理除了数组和反转后半段还有一种思路是用递归。递归的核心思想是用一个外部指针先走到链表末尾然后在回溯过程中和从头开始的指针逐一比较。这个思路本质上是用系统栈来模拟“倒着读链表”的过程但写法比较抽象而且栈的深度就是链表长度当链表长度为 10 万时递归深度 10 万很容易导致栈溢出Python 默认递归深度在 1000 左右所以 Python 里写递归会直接爆栈C 在 LeetCode 上 10 万深度也会比较危险。递归代码示例如下仅用于理解思路不推荐在本题使用class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: self.front head def check(node): if node: if not check(node.next): return False if node.val ! self.front.val: return False self.front self.front.next return True return check(head)这个代码的逻辑是check(node)先一直递归到链表的最后一个节点然后在返回的过程中把当前节点和self.front指向的节点比较。比如链表1 - 2 - 3 - 2 - 1第一次比较发生在最内层node是最后的1self.front是开头的1相等然后self.front后移下一层node是倒数第二个2和第二个节点2比较相等。以此类推。这种方法的优点是代码非常简洁而且完全不用手动写反转。缺点是递归深度等于链表长度在数据量大的情况下不适用。4.2 用栈判断简单但不够省空间还有一种思路是用显式的栈。先遍历链表把全部节点值压入栈再遍历第二遍同时从栈里弹出元素依次比较。这和数组法本质一样空间复杂度也是O(n)。不过栈法有一点比数组法更直观栈的后进先出特性天然符合“倒序”的概念。所以如果你在面试时突然忘了数组法的细节用栈也能很快写出来。栈法的代码class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: stack [] cur head while cur: stack.append(cur.val) cur cur.next cur head while cur: if cur.val ! stack.pop(): return False cur cur.next return True这个解法适合快速验证思路或者作为从数组法到反转法之间的过渡理解。4.3 各解法横向对比我把几种常见解法放在一张表里方便你一眼看清它们的差异。解法时间复杂度空间复杂度是否修改链表适用场景数组 双指针O(n)O(n)否入门理解快速 AC栈O(n)O(n)否思路直观适合现场快速写出递归O(n)O(n)递归栈否只适合链表很短的情况快慢指针 反转后半段O(n)O(1)是可恢复面试标准答案竞赛常用从这个表能看出最优解是快慢指针 反转后半段。它不仅空间是常数级而且不依赖递归深度能安全处理 10 万级数据。唯一的“缺点”是它会改变链表结构但面试中你只要说出“比较完可以再恢复原状”这个点反而会让人眼前一亮。5. 面试现场从写代码到讲清楚思路5.1 面试官会追问什么这道题在面试中出现频率非常高面试官通常会按下面这个路径追问“能不能用 O(n) 空间”——你先给出数组法或栈法这个不难。“空间能优化到 O(1) 吗”——这就是核心问题需要你说出快慢指针 反转后半段。“你能证明为什么快慢指针能找到中点吗”——这需要你解释两个指针的速度差一个一步一个两步当快指针到达尾部时慢指针恰好走了一半的路程。为了严谨你还可以说“当链表长度为奇数时慢指针落在正中间长度为偶数时快指针第一次越过尾部的回合慢指针落在中间偏右的位置这个偏右恰好是后半段的开始不需要额外处理。”“反转链表之后原来的链表还能恢复吗”——你可以说可以只要在比较结束后再反转一次后半段。但要记住如果你的代码里已经写了恢复逻辑那么返回值需要先存到一个变量里避免恢复过程影响返回值。“如果链表是单向的如何找到倒数第 k 个节点”——这是衍生问题和快慢指针同源。你能熟练处理回文链表这个问题也自然能答。5.2 常见错误与调试技巧我把自己在刷题和帮别人 review 代码时遇到的典型错误列一下。第一个错误是找中点时用了while fast.next and fast.next.next导致链表长度为奇数或偶数时中点位置不对。比如长度为 3 的链表有些写法会让slow停在第二个节点而不是正中间。如果你不确定自己的中点逻辑对不对最直接的办法是拿几个典型用例在纸上走一遍空链表、单节点、双节点、三节点、四节点、五节点。第二个错误是反转后半段时丢失了头节点或者反转后不知道用什么指针来遍历。反转链表的标准写法是prev、cur、nxt三个指针每次先保存nxt cur.next再改cur.next prev然后整体右移。很多新手容易忘掉“先保存 next”这句导致链表从中间断掉。第三个错误是忘记处理偶数长度下right为空的情况。如果你把比较循环写成while left and right或者while left ! right需要注意奇数长度时中间节点是否导致多比较一次。我用while right就是为了避免这个问题。调试这类链表问题时我推荐一个很实用的技巧写一个辅助函数把链表打印成数组形式比如def show(head): res []; while head: res.append(head.val); head head.next; return res。当你对反转结果不确定时就打印出来看看。虽然刷题时不能打印实际上可以打印LeetCode 控制台不会管你但本地调试效果很好。5.3 相关变种题拓展回文链表有很多变种刷完这道题之后可以顺手做几道关联题目把知识串起来。206. 反转链表回文链表的后半段反转就是 206 的应用。876. 链表的中间结点回文链表的第一步就是找中点876 专门练这个。143. 重排链表这类题同样需要找中点 反转后半段然后用双指针交替连接是回文链表思路的进阶版。19. 删除链表的倒数第 N 个结点快慢指针的另一个经典应用练完回文链表再做会非常顺。这几道题如果能连着刷完你对“链表双指针 反转”的理解会明显上一个台阶。虽然 LeetCode 题目很多但很多题其实都是常见思路的排列组合。234 这道题就像一把钥匙把基础链表操作的常见组合都带出来了。我个人做了很多道链表题之后的体会是回文链表这道题的解法选择和面试表现非常相关。如果在面试中你直接写了反转后半段的解法并且能边说边写把每个变量的作用解释清楚面试官会认为你的代码基本功很扎实。反之如果只写数组法虽然也能过但给面试官留下的印象会逊色不少。最后再分享一个小技巧如果你在面试或比赛中时间紧张可以直接先写数组法再口头说明“我可以优化成 O(1) 空间做法是找中点后反转后半段”这样既保证了正确性也展示了你对优化方向的理解。然后如果面试官让你继续你再动手写最优解。这种“先给保底再露实力”的策略比一上来就硬啃最优解要稳妥。希望这篇拆解能让你把 234 题彻底拿下后续再遇到链表相关的题目也能更从容。