回文链表：快慢指针与原地反转的最优解

回文链表这道题LeetCode第234题可以说是链表入门到进阶之间的一道分水岭。我刷题断断续续好几年面试别人时会拿它当试金石自己也翻来覆去写过不少版本每次重写都有新体会。题目本身一句话就能讲清楚——判断一个单向链表是不是回文结构但真正想写出让面试官满意的答案背后涉及快慢指针找中点、链表原地反转、边界条件处理这些基本功的排列组合。今天就把这道题从最朴素的解法到最优解连同我踩过的坑一起捋一遍。1. 先把题读懂回文链表到底在考什么1.1 回文的概念迁移到链表回文大家最早都是在字符串里接触的。上海自来水来自海上这种正读反读都一样的结构放到数组里判断非常简单左右两个指针一个从头部往右走一个从尾部往左走逐个比对字符就行。数组支持随机访问尾部指针可以直接定位所以这个问题在数组语境下几乎没有难度。但链表不一样。单链表每个节点只有指向下一个节点的指针你拿到了头节点只能一路往next走没法回头。这就带来一个天然的信息不对称我想比较第一个节点和最后一个节点但最后一个节点在哪里需要遍历到末尾才知道等我走到末尾了又没有prev指针可以往回去。这是回文链表这道题最核心的矛盾点——单向链表的不可回退性。LeetCode原题要求的输入是单链表节点定义通常是public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }题目会给你类似1 - 2 - 3 - 2 - 1这样的链表要求返回 true而1 - 2 - 3则返回 false。注意节点值可能是正数、负数、重复值这些都影响判断逻辑的设计等下我会专门讲边界测试。1.2 进阶要求才是这道题的精髓题目附录里有一行进阶描述你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题这行字才是真正的考点。很多初学者第一反应是把链表转成数组或者 ArrayList然后用数组的双指针法这确实能通过所有测试用例但空间复杂度是 O(n)等于避开了题目真正想考察的东西。为什么面试官喜欢这道题因为它刚好把链表题里三个最高频的考点串在了一起快慢指针找中点、链表反转、双指针比较。如果这三样你都熟练这道题就是送分题如果哪一样生疏当场就会卡壳。这也是我说它是分水岭的原因。所以接下来先从最直白的解法讲起再从复杂度角度一路优化到符合进阶要求的解法。2. 舒适区解法值收集加双指针为什么只能算及格2.1 思路和代码实现既然链表的痛点是不能从后往前访问那我们就解决这个痛点——把链表的值全部复制到一个支持随机访问的容器里。ArrayList 的 get(index) 是 O(1) 的拿到数组或列表之后回文判断就是纯粹的左右指针游戏。public boolean isPalindrome(ListNode head) { ListInteger vals new ArrayList(); ListNode cur head; while (cur ! null) { vals.add(cur.val); cur cur.next; } int left 0; int right vals.size() - 1; while (left right) { if (!vals.get(left).equals(vals.get(right))) { return false; } left; right--; } return true; }代码逻辑非常直白第一次遍历把节点值依次装进列表第二次分别从两端取值比较。这个解法的正确性毋庸置疑LeetCode 上直接提交也能通过。如果你在笔试环节时间紧张写这个版本完全没问题至少能 AC。2.2 这个方案的问题在哪里问题出在两个层面。第一是空间复杂度。假设链表有 n 个节点ArrayList 底层是数组扩容后需要存储 n 个 Integer 对象在 Java 里这还不止 O(n) 那么简单——Integer 是包装类型每个元素有对象头开销实际内存占用可能在 16 字节以上比链表节点本身还重。如果链表长度是几百万这个方案会吃掉可观的内存。第二是它没有触碰到题目的核心技能点。你在面试里写出这个解法面试官大概率会追问一句你的空间复杂度是多少能不能做到 O(1)这时候你如果答不上来前面代码写得再顺也会扣分。我见过太多候选人卡在这个追问上本质是只停留在能跑通的层面没有深入思考链表结构本身的特性。补充一点如果你非要用辅助容器可以用遍历一次的方式同时完成比较也就是栈方案——前半段入栈后半段依次和栈顶比较。这种方法空间复杂度依然是 O(n)而且栈的写法容易在指针边界上出错说实话并不比 ArrayList 方案高明。它唯一的好处是展示了用栈实现反向访问的思路这也是后文递归解法的雏形。3. 面试官想看的解法快慢指针加反转后半段3.1 方案选型的底层逻辑既然不引入额外容器那就得想办法让链表自己长出反向访问的能力。链表题里反向访问的标准答案是什么反转。如果我们把后半段链表原地反转让原来末尾的节点变成新的头节点那么从新头节点出发沿 next 一路走实际上就是从原链表的尾部向中间走。再把前半段从头开始走两条路线正好在同一点相遇逐节点比较即可。这里有两个问题需要解决第一如何找到链表的中间节点第二如何只反转后半段而不影响前面部分的遍历第一个问题的标准工具是快慢指针快指针每次走两步慢指针每次走一步快指针到达末尾时慢指针恰好走到中间。第二个问题则需要一次严谨的原地反转指针操作。为什么选择反转后半段而不是反转前半段因为反转前半段会破坏从头开始的路径你没法再用原始的 head 做左半段的遍历了。反转后半段则保留了 head 原本的起点整个比较过程只需要一个变量记录后半段反转后的新头节点逻辑更清晰代码也更不容易写错。3.2 快慢指针找中点的细节先看找中点的写法ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }循环结束后slow 指向的位置取决于链表长度。如果链表是奇数长度比如1 - 2 - 3 - 2 - 1slow 会停在正中间的元素 3 上如果链表是偶数长度比如1 - 2 - 2 - 1slow 会停在第二个 2 上也就是右半段的起点。这个细微差别极其重要。奇数长度时中间节点不需要参与比较因为它和自己回文偶数长度时slow 本身就是右半段的第一个节点。换句话说无论奇偶slow 最终指向的节点都是后半段需要反转部分的头节点。这个统一性正是很多解法代码看起来很短的原因。另一个容易踩的坑是快指针的循环条件。有人写成while (fast.next ! null fast.next.next ! null)这种写法在链表长度为偶数时会让 slow 落在偏左的位置导致后续比较区间错位。推荐的写法就是在上面那行先把 fast 和 fast.next 判空再决定是否移动这样对任何非空链表都安全。3.3 反转后半段链表找到后半段头节点 slow 之后我们要把从 slow 开始到链表末尾的这一段原地反转。标准的反转链表模板是三个指针轮转ListNode prev null; ListNode cur slow; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; }循环结束后prev 就是反转后的新头节点。例如原链表1 - 2 - 3 - 2 - 1slow 指向 3反转从 3 开始的后半段后原链表变为前半段1 - 2 - 33 的 next 被改为 null后半段反转后1 - 2实际上是从原尾部开始的1 - 2pre 指向这个 1等一下这里我要解释得更精确一些。原链表1 - 2 - 3 - 2 - 1slow 是正中间的 3反转从 slow 开始的部分实际是把3 - 2 - 1变成1 - 2 - 3但原来的 3中间节点反转后变成了尾巴且它的 next 是 null。此时链表结构被改成了1 - 2 - 3 - null和1 - 2 - 3 - null两条链非也更准确地说原链表被拆成了两条链左半链head - 1 - 2 - 33 的 next 为 null 右半链prev - 1 - 2 - 33 的 next 为 null两条链共享了中间节点 3 这个值但实际是原地修改了指针所以没有额外空间。比较时左指针从头开始走右指针从 prev 开始走遇到不等就返回 false直到右链走到尾部。对于偶数长度1 - 2 - 2 - 1slow 指向第二个 2反转2 - 1得到1 - 2。左链是 1 - 2右链是 1 - 2正好一一对应。3.4 完整代码与复杂度分析把上面三步拼起来完整解法如下public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } // 1. 快慢指针找中点 ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 2. 反转后半段 ListNode prev null; ListNode cur slow; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; } // 3. 双指针比较 ListNode left head; ListNode right prev; while (right ! null) { if (left.val ! right.val) { return false; } left left.next; right right.next; } return true; }时间复杂度找中点走 n/2 步反转走 n/2 步比较走 n/2 步总共是 O(n)。空间复杂度只用了几个指针变量没有额外容器是 O(1)完全满足进阶要求。这里有一个我很容易忘记讲的点如果面试官要求你不能破坏原链表结构也就是函数执行完链表要恢复原样那你就得在比较完后把后半段再反转一次接回去。做法挺简单比较结束之后对 prev 指向的链表再做一次反转恢复到 slow 原本的位置即可。LeetCode 原题没有这个要求但我在真实面试中被问到过一次当时确实愣了一下。建议你把恢复链表的这段代码也练熟备着不亏。4. 边界情况与实操中踩过的坑4.1 测试用例清单写算法题边界条件怎么设计直接反映你有没有系统训练过。回文链表这题我建议至少测下面几组场景输入示例期望结果空链表nulltrue单节点1true双节点回文1 - 1true双节点非回文1 - 2false奇数长度回文1 - 2 - 1true奇数长度非回文1 - 2 - 3false偶数长度回文1 - 2 - 2 - 1true偶数长度非回文1 - 2 - 3 - 4false全部相同值1 - 1 - 1 - 1true负数混合-1 - 2 - -1true空链表和单节点是很多解法第一行就 return true 的原因因为空链表和只有一个节点的链表天然是回文。不要小看这个 base case少了它快指针fast.next会直接空指针异常。4.2 我在写这题时踩过的坑第一个坑是反转链表时忘记保存 next 指针。cur.next一旦被改写原来的后继就丢了必须先用临时变量存起来。这是我早期写反转链表的标配错误后来养成习惯在修改 cur.next 之前永远先执行ListNode next cur.next想都不用想。第二个坑是奇偶长度下 slow 位置带来的比较边界问题。有些网上的写法用fast.next.next作为循环判断条件导致奇数链表时 slow 落在中间偏左结果比较完左链后右链还没遍历完多出了一个多出来的节点报错还不知道错在哪。我的经验是统一用fast ! null fast.next ! null这样 slow 在奇数时落在正中间在偶数时落在右半段起点反转右半段后while (right ! null)这个循环天然正确因为右链一定不比左链长。第三个坑是值比较用还是equals。链表节点定义中 val 是 int 基本类型所以left.val ! right.val是正确的。但如果你在写别的语言的版本时比如 Python 或者 Java 里误把 val 当成 Integer 对象在 -128 到 127 之间可能碰巧正确超出这个范围就出问题。所以我的建议是看清楚节点定义基本类型直接用!包装类型用 equals 方法。第四个坑是我在练习时发现的题目要求判断回文但并没有保证你可以修改链表所以某些在线评测环境里如果你把链表结构改了后续用例可能会受影响。LeetCode 每个用例都会重新构建链表所以问题不大但如果是公司内部的在线笔试一个用例的链表可能被多个断言共用破坏原链表结构会导致奇怪的现象。这也是为什么我强调恢复链表这个操作值得准备。4.3 调试技巧分享如果你在本地调试这道题可以写一个辅助方法把链表打印出来特别是反转后打印两条链的内容。我看到不少人卡住是因为对反转后半段之后链表长什么样没有直观概念。我自己调试时的做法是定义void printList(String tag, ListNode head)方法输出每个节点的 val然后在反转前后各调一次。看到两条链了就很容易理解为什么比较循环要用right ! null而不是left ! null作为终止条件。另外提一个细节比较循环的终止条件用right ! null就足够不需要同时判断 left。因为左右链长度相同奇数时左链多一个中间节点但右链先走到 null循环结束只要右链走到头说明所有需要比较的节点都已经比过了。5. 面试答题节奏与扩展思考5.1 面试中怎么答才加分很多候选人拿到这道题上来就闷头写最优解其实不是最好的策略。面试官想看的往往不只是最终代码而是你的思考过程。我的建议是分三步走先明确问题确认链表是单链表还是双向链表节点值会不会溢出能不能修改链表结构。这些提问本身就展示了你对细节的敏感度。然后给出暴力解法主动说出它的复杂度顺势引出优化方向。你可以这么说最直接的方法是把值复制到数组做双指针时间是 O(n)空间是 O(n)。但题目进阶要求 O(1) 空间所以需要原地解决思路是找到中点、反转后半段、再比较。最后再写代码。写的时候边写边用小注释解释每一步的目的比如这里快指针走两步慢指针走一步为了找中点。这么做的好处是即使你在细节上犯了一个小错面试官也知道你的整体方向是对的更愿意给提示而不是直接否定。时间复杂度分析一定要算给他听找中点 n/2反转 n/2比较 n/2加起来还是 O(n)。空间是 O(1)。这里顺便可以展示一下你对原地算法的理解——只用了常数个指针变量没有随输入规模增长的内存分配。5.2 相关变式与延伸回文链表这个本质思路可以延伸到不少变种题。第一个变式是删除一个节点后能否成为回文链表。这类题会让你返回布尔值判断删掉某一个节点后剩余部分能否构成回文。做法可以先找到第一个左右不一致的位置然后分别尝试删除左边或右边那个节点再检查剩余部分。本质上还是双指针加回文判断但多了一个跳过节点的技巧。第二个变式是环形链表里找回文或者说判断链表是否有环之后再判断回文这属于把链表其他考点混进来的综合题基本思路不变但需要先处理环的问题。第三个值得提的是递归解法。用递归天然实现了从后往前的访问顺序代码看起来极其精简private ListNode front; public boolean isPalindrome(ListNode head) { front head; return recursiveCheck(head); } private boolean recursiveCheck(ListNode head) { if (head null) return true; boolean isPal recursiveCheck(head.next); if (!isPal || front.val ! head.val) return false; front front.next; return true; }这个写法的时间复杂度是 O(n)但递归调用栈空间也是 O(n)不满足进阶要求。不过它对理解递归和链表的关系很有帮助。如果你在面试里时间充裕可以把这个解法作为另一种思路提一下然后明确说出它的空间开销展示你对不同方案边框边界的认知。这类链表题的母题还有几个值得一起刷反转链表206、链表中倒数第 k 个节点剑指 Offer 22、环形链表141、合并两个有序链表21。你会发现这几道题反复用到快慢指针、反转、边界处理一套基本功练熟之后很多新题就是换皮。最后分享一点个人的刷题体会这题我前前后后写过的版本少说也有七八个变体。最初只会 ArrayList后来学会了快慢指针但总在奇偶长度上出错再到能在五分钟内把最优解完整写出来并顺手讲清思路中间隔着的其实就是对指针操作的理解深度。建议大家不要满足于提交通过这一个目标可以试着在本地把两种解法都实现一遍再把最优解的执行过程用链表图手画一遍让每个 next 指针的指向变化都在脑子里有画面感。链表的操作就是这样画着画着就通了。等你把这种思维练成条件反射回文链表就不是什么难题了它只是你链表基本功的一次小检验而已。