刷LeetCode Hot100刷到第21题碰到了回文链表。这道题我印象特别深因为早年校招面试的时候被问过那时候我张口就是“转成数组两个指针往中间走”面试官马上补了一句“如果不让你用额外空间呢”我愣在原地。后来真正把链表的快慢指针和反转链表玩明白之后才发现这道题根本不难它只是把两个最基础的链表操作组合在了一起而这两个操作几乎能贯穿所有链表题的中后期刷题路线。这篇文章我会完整复盘这道题的解法演进、最优解细节、我提交过程中真实踩过的坑以及这套“找中点反转”组合拳在其他题目里的迁移用法。1. 先看懂题目在考什么回文链表的本质是“对称性”1.1 题目本身的定义回文链表输入是一个单链表的头节点head要你判断这个链表从前往后读和从后往前读是不是相同的序列。比如1 - 2 - 2 - 1是回文1 - 2不是回文。力扣给的函数签名是def isPalindrome(self, head: Optional[ListNode]) - bool:看起来非常短但如果你只看过一次题解就匆匆提交很容易漏掉它背后的两个隐藏要求能不能做到时间复杂度 O(n)能不能做到空间复杂度 O(1)1.2 为什么数组题的解法不能直接平移过来回文串大家很熟双指针从两端往中间走就行因为数组/字符串支持随机访问arr[i]和arr[n-1-i]可以直接拿出来比。链表不行你没法从尾部往前跳。我第一次做这题时本能地想“那就先遍历一遍存进数组再双指针比较”这当然是对的也能 ACAccepted但这只证明了你会写双指针没证明你懂链表。链表题的核心矛盾永远是只能从 head 开始沿着 next 单向走没有办法回头。想判断回文本质上是想从两端“同时”往中间比较可链表天然的遍历方向只有一个。所以要解决这个问题要么借助额外空间把顺序存下来要么想办法让链表的“后半段”能够从尾往头走——后者只能通过反转链表实现。1.3 这道题真正锁定的三个技术点我反复刷了多遍之后把这道题的考核点拆成三块找链表中点经典快慢指针快指针走两步、慢指针走一步快指针落到链表尾部时慢指针正好落在中间附近。反转链表三指针 pre、cur、nxt把后半段原地反转得到一个新的“反向头节点”。对称比较一个指针指向前半段头节点一个指针指向反转后的后半段头节点逐个比对 val。这三个点单拎出来都是链表题里的“基本动作”回文链表只是把它们串起来。这也就是为什么 Hot100 里会收录它不是因为它难而是因为它覆盖面广属于“一题练三招”的典型题目。2. 三种解法大盘点先把保底方案写出来再谈优化2.1 转数组 双指针最容易想但空间不是 O(1)先用一个数组把所有节点值存下来然后一个指针从头、一个指针从尾往中间靠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这个方案的好处是 3 分钟就能写完几乎不会出错。时间 O(n)空间 O(n)。如果是笔试抢时间写这个完全没问题。但如果是面试场景面试官大概率会追问一句“能优化到 O(1) 空间吗”所以只掌握这一种肯定不够。2.2 递归反向比较代码最短但不推荐作为主答案利用递归可以让函数在“归”的过程里从链表尾部开始往前处理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 self.front.val ! node.val: return False self.front self.front.next return True return check(head)这个写法看起来非常惊艳但有两个问题一是递归深度等于链表长度长链表比如十万个节点在力扣本地测试环境可能直接栈溢出二是空间复杂度依然是 O(n)与转数组方案没有本质区别。所以我建议只在脑暴时提一句“递归也能实现”真要写最优解还是回到迭代。2.3 快慢指针 反转后半段面试的标准答案整体思路一句话找到链表中点把中点之后的链表原地反转然后从两头开始逐个比较。因为后半段被反转后它的“头”其实就是原链表的“尾”这样就能做到不借助额外数组从两端同时往中间移动。三种方案对比如下方案时间复杂度空间复杂度优点缺点转数组 双指针O(n)O(n)直观、不易出错不符合 O(1) 空间要求递归反向比较O(n)O(n)代码短深度大时可能爆栈快慢指针 反转后半段O(n)O(1)最优解、面试加分边界条件稍多需要熟练可能有同学会问“反转链表本身不也是 O(1) 空间吗”对反转链表的迭代写法只需要固定几个临时指针变量不随链表长度增长所以整体空间是 O(1)。3. 最优解全流程拆解找中点、反转到比较每一步都讲清楚3.1 可以直接提交的完整代码先给出一版我在力扣上验证通过的标准写法# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: 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 # 第二步反转后半段链表 prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt # 第三步前半段与反转后的后半段逐个比较 left head right prev while right: if left.val ! right.val: return False left left.next right right.next return True这段代码里有个很容易让人困惑的地方为什么反转是从slow开始而不是从slow.next开始我下面详细解释一下。3.2 快慢指针找中点fast 走到头时slow 到底在哪先看快慢指针的移动规则slow每次走一步fast每次走两步。循环停止条件是fast为空或者fast.next为空。我用两个例子走一遍偶数长度1 - 2 - 2 - 1fast 最终为空slow 最终停在第二个2上也就是右半段的开头。奇数长度1 - 2 - 3 - 2 - 1fast 最终停在最后一个节点非空slow 最终停在正中间节点3上。注意在这版写法里我没有区分奇偶长度而是直接让 slow 停在“右半段开头”。偶数长度时slow 就是右半段头奇数长度时slow 是正中间节点。关键点在于反转从 slow 开始相当于把中间节点也拉进了后半段一起反转。比较时左半段对应的末尾其实也是中间节点两边比较到中间时会拿“同一个值”比一次不会出错。这比很多题解中“if fast: slow slow.next”的写法更省事因为少了一个对奇偶的判断分支理解起来反而更顺只要记住后半段包含“slow 开始往后的所有节点”。3.3 反转后半段三指针中 nxt 的作用为什么不能省链表反转的迭代写法是这道题的第二大考点。核心是三个指针prev已经反转好的新链表头初始为 Nonecur当前正要处理的老链表头nxtcur 的下一个节点保存起来防止断链。每轮做三件事把cur.next指向prev然后把prev挪到cur再把cur挪到nxt。如果漏了nxt当你执行cur.next prev时per原链表中 cur 后面的节点就找不回来了这是初学者最容易犯的错误。反转结束后prev指向的是反转后后半段的头cur指向 None。用生活化类比的话这就像你手里拿着一串项链要从中间开始把后半截反过来重串每一步都必须先记住下一颗珠子在哪否则一松手就散架了。3.4 对称比较为什么循环条件用 while right 而不是 while left比较阶段有两个指针left从原链表 head 出发right从反转后的后半段头出发。循环条件用while right有一个很自然的原因如果链表是回文那么反转后的后半段长度一定不大于前半段长度只要 right 还没走完就说明还有节点需要比较一旦 right 走完说明后半段所有节点都已经在前半段找到对应且相等可以返回 True。这里不要用while left因为前半段可能比后半段长一个节点奇数长度时中间节点也在后半段被反转了但左指针要走到最后才结束如果用 left 做条件会多做一次多余的比较虽然多数情况下结果也能对上但逻辑上不如 right 清晰。3.5 一个必须回答的 follow-up要不要恢复原链表LeetCode 234 本身没有要求“不能修改链表”所以多数题解提交时不会恢复链表。但在真实面试里面试官常常会追加一句“你的代码把链表后半段反转了如果调用方之后还要用这个链表怎么办”标准回答有两种第一种再反转一次恢复。比较结束后照着刚才的反转逻辑再对后半段做一次反转把链表拼回原样。代价是额外 O(n) 时间空间仍是 O(1)。第二种反转前不修改原结构而是复制后半段节点。但这就引入了 O(n) 空间属于空间换时间不如第一种。我个人建议至少在本地写好“恢复链表”的代码面试时主动提一句“这里修改了输入结构如果需要保持原链表不变我可以再反转一次恢复”这比等面试官追问表现得更好。4. 边界条件与真实提交踩坑这些细节我替你试过错4.1 空链表与单节点链表要提前返回当head为空或head.next为空时直接返回 True。这里没什么技术含量但很容易被忽略。力扣给的测试用例里有空输入也有[1]这种单节点用例不写这句的话要么报空指针错误要么在后面的循环里出现诡异行为。4.2 奇数长度和偶数长度对 slow 的影响用一个例子记住很多题解会额外写一句if fast: slow slow.next它的意图是如果 fast 不为空说明链表长度是奇数slow 正停在中间节点需要再往后走一步才能真正指向“右半段的头”。这和我前面给的代码风格不同我给的版本是反转slow本身开始的节点。两种写法都能 AC但我个人强烈推荐“反转从 slow 开始”的版本因为少一个 if 分支代码更短不需要记忆“奇数加一、偶数不加”的规则奇数长度时中间节点参与比较相当于自己和自己比不影响正确性。如果你在面试时写的是if fast: slow slow.next 反转 slow那你要特别小心[1, 2]这个用例。我见过不少人在这一步翻车[1, 2]是偶数长度fast 最终停在 None所以不会执行 slow slow.nextslow 停留在 2反转从 2 开始得到[2]比较时1 ! 2返回 False正确。但如果你的反转起点是从slow.next开始同时 fast 为 None那在[1, 2]上就会出问题slow 停在 2slow.next是 None反转结果是空链表比较循环根本进不去直接返回 True错误。这一点务必在某 IDE 里自己跑一遍。4.3 反转后半段时不要动 head 的指向有同学图省事在反转前先把 head 存下来然后直接复用 head 变量去走反转结果最后比较的时候发现 head 已经跑到链表中间了怎么都 AC 不了。反转时一定要新定义prev、cur、nxt指针原链表的 head 和 slow 都不要动。我的习惯是反转前再给 slow 起个别名比如second slow后面操作 second这样读代码的人一眼就能分清“原链表”和“反转链表”两个体系。4.4 我调试时用的本地测试用例集合力扣提交前我会先把这些用例在本地跑一遍覆盖所有主要分支[]空链表期望 True。[1]单节点期望 True。[1, 2]偶数长度非回文期望 False。[1, 2, 2, 1]偶数长度回文期望 True。[1, 2, 3, 2, 1]奇数长度回文期望 True。[1, 2, 3]奇数长度非回文期望 False。[1, 1, 1, 1, 1]全部相同期望 True。每次写完链表题我都会留一套这样的模板用例因为链表题最怕的就是边界条件翻车依赖力扣的报错来调试会浪费大量提交次数。5. 技巧迁移同一套“找中点 反转”组合拳还能解哪些题5.1 先记住这个可复用的操作模板链表题里有一批高频题本质上共用同一个套路# 模板快慢指针找中点 slow head fast head while fast and fast.next: slow slow.next fast fast.next.next拿到 slow 之后你可以做很多事反转 slow 之后的部分回文链表把 slow 之后的部分和前半段交叉合并143. 重排链表以 slow 为分界点处理环形链表的入口142. 环形链表 II直接返回 slow876. 链表的中间结点。所以我一直觉得回文链表最大的价值不是它本身而是它逼你把“找中点”和“反转链表”这两个动作练到条件反射。我刷到 Hot100 后半程时好多链表题写着写着发现又是在调用这两个基本功。5.2 用同一套思路解 143. 重排链表重排链表要求把L0 - Ln - L1 - Ln-1 - ...这样交错重排。解法步骤是快慢指针找到中点反转后半段两个链表交叉拼接。你发现没有前两步就是回文链表的前两步第三步只是把“比较 val”换成了“交替改 next”。如果你把回文链表真的吃透了重排链表就是换汤不换药。5.3 面试时的表达顺序建议如果面试官考这道题我建议按这个顺序表达先说最直觉的数组法把回文定义翻译成“首尾相等”并指出空间 O(n) 不是最优再说可以优化到 O(1) 空间思路是“让后半段可以反向遍历”所以需要找中点 反转手写代码前先画出链表结构图标出 slow、fast 的移动轨迹写完代码后手动跑[1, 2]和[1, 2, 1]两个用例主动验证边界。这套顺序既能展示你的思路演进又能体现你考虑边界条件的习惯。很多候选人代码能 AC但讲不清为什么 slow 会停在那个位置面试官稍微追问就露馅。5.4 遇到“能否不破坏链表结构”时的延伸想法如果你还有余力可以顺手想一想如果不反转链表有没有其他 O(1) 空间的方案严格来说比较两段不在同一内存布局的链表不借助额外存储、又不修改链表的话目前没有比“反转 恢复”更实用的办法。所以业内普遍接受的答案就是反转后半段比较完再恢复。这也是为什么我说“会反转链表”是这道题默认要求掌握的能力。我实际刷题下来最大的体会是链表题不要贪多把 206 反转链表、876 中间节点、234 回文链表、143 重排链表这四道连在一起刷一遍比分散刷二十道效果更好。它们像同一棵树上的几根枝干根是同一个快慢指针和三指针反转。今天写的 234 回文链表就是把这几个枝干拧成一股绳的地方。你如果能把这里的每一步边界都讲清楚那 Hot100 里绝大多数链表题对你来说都只是换个壳子而已。