不少朋友第一次刷这道题第一反应是“回文把链表转成数组不就行了”——这个思路没错但如果你只答这一种解法面试基本就停在及格线了。作为一道几乎所有题库都会收录的经典链表题#234 回文链表考察的是三个基本功链表遍历、双指针找中点、单链表反转。这篇我把四种主流解法拉开讲清楚从最容易想到的辅助数组到空间 O(1) 的最优解每一步里有哪些容易踩的坑、面试官会顺着什么方向追问都一起写了。适合正在刷算法题、准备技术面试的朋友也适合想巩固链表基础、把手写反转链表练到条件反射的开发者。题目本身不难但能把这道题讲出自洽的优化路径面试里会很加分。1. 题目理解与核心思路拆解1.1 “回文”在链表场景下到底难在哪回文的定义很简单一个序列正着读和倒着读完全一致。判断一个数组是不是回文双指针两头往中间夹就行因为数组是随机访问结构拿到首尾下标后访问成本一样。但链表是单向的你从 head 能走到 tail却没法从 tail 直接回到 head也不存在 O(1) 的下标访问。假如硬要套数组双指针的思路每次让一个指针从头走到指定位置整体复杂度立刻退化成 O(n^2)这在面试里是会被直接追问的重伤。打个比方数组像一排编了号的小抽屉你要第几个一伸手就到链表像一串珍珠你只能顺着线一颗颗摸过去想从中间往后比较必须先把中间那颗珠子找到。这个结构差异就是这道题一切思路的来源。很多人初看题目会觉得这不就是个遍历吗实际上链表的单向性让“反向比较”变成了核心矛盾。你要判定回文本质上需要一趟从尾部到中部的比较而链表不给你反向遍历的能力。理解了这一点后面所有解法其实都是围绕“如何低成本地反向访问链表”展开的数组法用随机访问替代反向遍历栈用 LIFO 特性天然反向递归用系统栈延迟判断最优解则干脆把后半段反向——四种思路殊途同归。1.2 题目背后的三个隐藏考点#234 表面上只问“是不是回文”实际上考了三层边界处理空链表和单节点链表天然是回文这两个 case 一上来就要考虑。空间复杂度意识进阶要求空间 O(1)意味着不能用数组、栈、递归这样的额外存储必须原地完成判断。链表操作基本功找中点、反转链表、必要时恢复链表每一项都是单独高频考点。这三个考点组合在一起决定了你在面试中的回答路径先给一个暴力解法证明你理解问题再逐步优化到 O(1) 空间。真实面试中大多数候选人能回答出两三种解法但能在黑板上把反转链表恢复原状、并把奇偶长度边界讲清楚的人少得多。这篇文就是想让你成为后者。还有个容易被忽略的细节题目要求的“回文”是对节点 val 的比较不是引用比较所以值相等即可不需要考虑节点地址。对于自定义类型节点比较逻辑可能要重载判等但算法骨架不变。2. 辅助数据结构方案先把思路跑通2.1 数组转存法最容易想到的方案遍历一遍链表把所有节点的 val 存入一个数组然后用双指针从两端向中间判断。代码非常短bool isPalindrome(ListNode* head) { vectorint vals; while (head) { vals.push_back(head-val); head head-next; } int left 0, right vals.size() - 1; while (left right) { if (vals[left] ! vals[right]) return false; left; --right; } return true; }这个做法的时间复杂度 O(n)空间复杂度 O(n)能正确通过所有测试用例。面试时我建议把它作为“第一步答案”正常给出这一步的意义是证明你理解回文判定本身而不是一上来就憋大招。不过你要意识到它的两个局限。第一是空间不满足进阶要求面试官听到“O(n)空间”大概率会追问“能不能优化”。第二是它没有发挥链表结构的特点等于把链表退化成了数组换个输入是数组还是链表代码几乎没差别。所以在面试叙述里我会这么铺垫“先用数组法确认问题定义然后我们再讨论不用额外空间怎么做”——这种表达能展示你的思考路径而不是直接甩最优解。顺便说一句如果链表节点值不是整数而是字符串数组法依然成立只是内存占用更大、比较成本更高真正需要关注的是比较逻辑是否支持判等。这个后续章节会展开。2.2 栈辅助法利用后进先出特性数组法的本质是“先随机访问再比较”栈辅助法的本质是“用栈把链表尾部变成可访问的顶部”。具体做法遍历链表把每个节点的 val 压入栈再从头遍历一次每次弹出栈顶元素与当前节点值比较不相等就不是回文。bool isPalindrome(ListNode* head) { stackint st; ListNode* p head; while (p) { st.push(p-val); p p-next; } p head; while (p) { if (p-val ! st.top()) return false; st.pop(); p p-next; } return true; }栈辅助法时间 O(n)空间 O(n)但它有个可以优化的点其实不需要把所有元素压栈只压前半段就够了。用快慢指针找到链表的中点把前半段压栈然后从中点之后开始遍历和栈顶逐次比较。这种做法空间降为 O(n/2)虽然量级还是 O(n)但在代码里是一种值得写出来的改进能体现你对空间占用的敏感度。bool isPalindrome(ListNode* head) { if (!head || !head-next) return true; stackint st; ListNode* slow head; ListNode* fast head; while (fast fast-next) { st.push(slow-val); slow slow-next; fast fast-next-next; } // 奇数长度时slow 正好指向中间节点跳过它 if (fast) slow slow-next; while (slow) { if (slow-val ! st.top()) return false; st.pop(); slow slow-next; } return true; }写这个优化版的时候最需要注意的是奇偶长度的处理。上面代码里循环结束后如果 fast 不为空说明链表长度是奇数slow 指向的是正中间那个节点它和自己对称不需要比较所以直接slow slow-next。如果 fast 为空说明是偶数长度slow 已经指向右半段第一个节点直接开始比较。这个细节面试官一眼就能看出你懂不懂边界。3. 递归解法用系统栈换代码优雅3.1 递归怎么模拟“从尾部反向比较”递归的本质是后进先出。先递归到链表末尾再在回溯过程中逐层往外比较相当于用系统调用栈代替了上一节的显式栈。ListNode front; boolean recur(ListNode cur) { if (cur null) return true; if (!recur(cur.next)) return false; if (cur.val ! front.val) return false; front front.next; return true; } boolean isPalindrome(ListNode head) { front head; return recur(head); }当recur(cur.next)递归返回时cur 实际上是从链表倒数第一个节点、倒数第二个节点……依次回溯的而 front 指针从 head 开始同步往后走这样一前一后、一右一左就完成了对称比较。这个思路很优雅但代价非常明确递归深度等于链表的节点数空间复杂度是 O(n)而且当链表非常长时可能引发栈溢出。很多人误以为递归“没有额外空间”实际上系统调用栈一样在占内存只是不用你手动管理而已。所以在分析空间复杂度时务必把递归栈深度算进去这也是算法面试的基本功。3.2 为什么它不是最优解把递归解法放在这里不是让你面试时优先用而是提醒你它和显式栈本质上是一回事都需要 O(n) 辅助空间。面试官如果明确要求空间 O(1)递归方案直接出局因为它连“用循环代替递归”的基本优化方向都满足不了。而且递归解法还有一个工程隐患某些语言的默认调用栈深度只有几千到几万层链表长度稍微大一点直接 Stack Overflow。相比之下显式栈用的是堆内存虽然也是 O(n) 空间但至少不容易爆栈。所以我的看法是递归版可以作为思路拓展提一句展示你知道“反向遍历可以用调用栈实现”但不要拿它当主答案也不要在没有把握的时候用毕竟它既不是最优解又在极端输入下不稳定。如果你在面试里先讲了数组法面试官追问“还能怎么优化”你可以从“压栈”自然过渡到“只压一半”再引出“能不能连栈都不用”这样讲递归才有位置——放在“虽然可以写但空间不理想”的对比里而不是作为独立方案硬推。4. 最优解快慢指针 反转后半段4.1 三步拆解最终方案的思路分成三步先用快慢指针找到链表中点再反转后半段链表最后用两个指针分别从原头节点和“反转后的后半段头节点”出发逐一比较节点值。为什么反转后半段而不是前半段因为链表是单向的p1 从头出发为了让它和 p2 比较p2 必须从一个可以让“p2 前进”的起点出发。反转后半段后后半段原本的尾节点变成了 p2 的头节点p2 从头往后遍历数学上等价于从原链表尾部往中间遍历正好和 p1 从头部往中间遍历形成对称。完整实现如下ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; cur-next pre; pre cur; cur nxt; } return pre; } bool isPalindrome(ListNode* head) { if (!head || !head-next) return true; ListNode* slow head; ListNode* fast head; // 快慢指针找中点slow 最终指向左半段最后一个节点 while (fast-next fast-next-next) { slow slow-next; fast fast-next-next; } // 反转右半段 ListNode* right reverseList(slow-next); // 逐节点比较 ListNode* p1 head; ListNode* p2 right; bool result true; while (p2) { if (p1-val ! p2-val) { result false; break; } p1 p1-next; p2 p2-next; } // 恢复链表 slow-next reverseList(right); return result; }注意看我在返回前把链表恢复了。题目只要求“判断”很多解法并不会恢复原链表但工程习惯是不要破坏输入结构尤其是面试官可能接着问你“如果不恢复会怎样”。这个细节加上去是个白捡的加分点。4.2 快慢指针定中点的细节快慢指针找中点是个高频考点值得单独展开。原理是 fast 每次走两步slow 每次走一步当 fast 走到末尾时slow 刚好走到一半。但“一半”的定义和循环条件强相关这里有两个常见写法写法 A循环条件while (fast fast-next)ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } if (fast) slow slow-next; // 奇数长度跳过中间偶数长度如 1-2-3-4循环结束后 fast 为 nullslow 指向 3正好是右半段开头奇数长度如 1-2-3-4-5循环结束后 fast 指向 5非空slow 指向 3需要slow slow-next跳到 4。这种写法适合后面直接反转 slow 开头的链表。写法 B循环条件while (fast-next fast-next-next)也就是我在主代码里用的ListNode* slow head; ListNode* fast head; while (fast-next fast-next-next) { slow slow-next; fast fast-next-next; } // slow 指向左半段最后一个节点偶数长度 1-2-3-4slow 停在 2奇数长度 1-2-3-4-5slow 停在 3。无论奇偶slow 都天然指向“左半段最后一个节点”后面恢复链表时直接slow-next reverseList(right)非常自然不需要额外判断奇偶。两种写法各有拥趸我更推荐写法 B因为它的状态更统一slow 永远定位在需要接回的断点上。面试时如果你能把这个选择讲清楚面试官会认可你对边界条件的掌控力。4.3 反转链表与恢复的细节反转链表是这道题的另一个基础一定要练到条件反射。迭代反转三步法pre 指向前一个节点cur 指向当前节点每次先把 cur-next 存到 nxt再把 cur-next 指向 pre最后 pre、cur 各进一步。最容易犯的错就是忘记先保存 nxt直接把 cur-next 改了导致后续节点全部丢失。ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; cur-next pre; pre cur; cur nxt; } return pre; }为什么主代码里比较循环条件是while (p2)而不是while (p1)因为 p2 是后半段链表的头后半段长度要么等于前半段偶数长度要么比前半段少一个节点奇数长度。以 p2 是否为空作为终止条件天然避开了前半段多出来的那个中间节点也避免了空指针解引用。这个细节值得记一下很多人的第一版代码习惯写while (p1 p2)虽然结果也对但说明你对两个链表长度关系不够敏感。恢复链表时执行slow-next reverseList(right)就够了。right 是反转前的右半段头节点reverseList(right)把它恢复成原来的顺序再接回 slow-next链表就恢复了原状。注意这里 reverseList 的入参变成了 right而不是第二次反转后的头原因是 right 在第一次反转后已经被耗掉了吗实际上不是被耗掉而是 right 指针仍然指向原右半段头节点经过第一次反转后它变成了右半段的尾节点再次 reverseList(right) 就是以这个原头节点为入参把整段再反回去。这个概念写代码时容易绕晕多画几次图就好。5. 边界条件与现场调试实录5.1 最容易写错的三个边界边界问题是链表题的重灾区这道题有三个地方很容易翻车。第一空链表和单节点链表必须提前返回 true。如果不写if (!head || !head-next) return true;后面的fast-next可能会在 head 为空时直接空指针异常。单节点链表虽然在多数实现里不会崩但语义上必须单独处理。第二快慢指针循环结束后对奇数长度的处理。如果你用写法 A漏掉if (fast) slow slow-next;那么中间节点会被拿来回文比较。运气好时中间节点和自己比较总是相等导致错误被掩盖运气不好时如果比较循环条件写错反而报错。这种“看似能跑通但逻辑不对”的情况比直接崩溃更危险。第三两节点链表的判断。比如 1-1 是回文1-2 不是。如果你用写法 A两节点时 fast 从第 1 个节点出发走一步后 fast 为 nullslow 指向第 2 个节点逻辑正确。但如果你在循环里误写了while (fast-next)而不是while (fast-next-next)两节点时 fast 会走到尾节点后继续访问fast-next-next再次越界。这种错很隐蔽因为三节点、四节点时可能恰好不触发异常。5.2 测试用例与辅助函数实战中我习惯先写两个辅助函数一个是构造链表的一个是打印链表的。它们不占用额外空间吗当然占用但只在本地调试时用不算进算法复杂度分析。打印函数尤其适合验证恢复操作是否成功。ListNode* createList(initializer_listint vals) { ListNode dummy(0); ListNode* tail dummy; for (int v : vals) { tail-next new ListNode(v); tail tail-next; } return dummy.next; } void printList(ListNode* head) { while (head) { cout head-val ; head head-next; } cout endl; }针对这道题我会手动跑这些用例输入期望结果验证点空链表true空指针处理[1]true单节点[1,1]true最短偶数回文[1,2]false最短非回文[1,2,1]true奇数长度回文[1,2,2,1]true偶数长度回文[1,2,3,1]false不对称结构另外可以加一个全相同值的用例比如[1,1,1,1,1]这种输入即使代码有边界问题也容易碰巧通过是对逻辑严谨性的压力测试。现场调试时我最常遇到的问题是反转后半段后打印出来发现链表断裂或者多了环。解决方法是把slow、right、以及反转后的头节点都打印一遍逐个核对指针关系。链表题里“画图 打印”是最高效的排错组合比盯着代码看半个小时管用得多。6. 方案对比与面试官追问套路6.1 四种方法横向对比解法时间复杂度空间复杂度核心特点面试建议数组转存法O(n)O(n)最直观易理解开场答案栈辅助法O(n)O(n)代码短LIFO 天然反向过渡答案递归法O(n)O(n) 调用栈代码最简洁提及即可快慢指针 反转O(n)O(1)最优解考察基本功重点展示表格里有个容易被误解的点快慢指针法看起来遍历了不止一遍为什么时间复杂度还是 O(n)因为找中点一次、比较一次、恢复一次每次都是线性时间常数级别是 3 倍左右但整体量级还是 O(n)。空间 O(1) 是因为我们只用了几个指针变量不随输入规模增长。面试时讲最优解我建议按照“为什么朴素解法不行 → 怎么找到中点 → 为什么反转后半段 → 怎么恢复”的顺序讲逻辑链条完整面试官不会被你跳跃的思路带跑。很多人上来就写代码写得又快又对但面试官追问原理时答不上来反而扣分。6.2 面试官会顺着什么方向追问这道题的追问方向几乎是固定的提前准备好能省很多麻烦。第一个追问必然是“能不能把空间优化到 O(1)”这就是快慢指针法的入口。你要能解释清楚“链表无法反向遍历”是一切的根源而反转后半段是绕过这个限制的手段。第二个追问是“如果题目允许修改原链表呢”答案是“那就可以不恢复”但你应该主动补一句“不过工程上如果调用方还要用这条链表我倾向于恢复”。这个表态很重要面试官考察的是工程素养而不是解题快感。第三个追问是“如果是双向链表怎么判断回文”答案简单双向链表天然支持从尾到头遍历直接首尾双指针往中间夹就可以空间 O(1)时间 O(n)。这个追问变体我自己就遇到过属于送分题但如果你连双向链表和单向链表的差异都说不出反而减分。第四个追问更开放“如果链表节点存的是自定义对象比较逻辑要怎么做”这时候你需要指出核心思路不变只是把p1-val ! p2-val换成自定义判等逻辑如果对象支持序列化或者哈希还可以模块化比较。算法题到这一类考官实际是想看你抽象建模能力而不是单纯背书。还有一个拓展方向就是把回文判断延伸成回文子串、回文子序列那是另一类经典题目了和链表数据结构关系不大。面试时如果你能提一句“链表的特殊性在于不能随机访问所以子串类问题通常不会用链表出题”会显得你对数据结构选型有全局认识。一点实操体会最后分享点个人经验。我在实际刷题时第一遍总是先写数组法用最短时间确认逻辑正确再写快慢指针法对照两种实现的差异。这个习惯帮我避免了很多低级错误因为一旦最优解写挂了至少还有个正确版本兜底。调这种链表题最推荐的方法是拿张纸画一个五节点链表手动走一遍快慢指针和反转步骤。画三遍之后你自然能理解为什么while (fast-next fast-next-next)会让 slow 停在左半段末尾而不是中间节点。反转链表这个子操作我也建议单独练到条件反射不是背代码而是理解“保存 nxt → 改向 → 移动指针”这三步为什么缺一不可。如果你现在正在准备面试这道题一定不要只看答案。动手把四种方案都写一遍尤其是快慢指针 反转写到不用思考就能写对的程度。面试场上能把这道题讲出层次的人链表基础基本都不会差。