1. 题目解读与核心思路——这道题到底在考什么力扣热题100里的“回文链表”题号是234属于链表专题里一道非常经典的题目。你要是刷过链表系列绕不开它。我第一次做这道题的时候心里就一个念头判断回文不是数组的活儿吗怎么挪到链表上来考了后来才明白这道题真正的考点根本不是“判断回文”本身而是链表的操作基本功——找中点、反转链表、断链处理这三个动作才是面试官真正想看的。题目要求很简单给定一个单链表的头节点判断它是不是回文链表。回文的意思就是正着读和倒着读一样比如 1 - 2 - 3 - 2 - 1 就是回文而 1 - 2 - 3 - 3 - 2 就不是。数组判断回文左右双指针往中间走就行但链表不行因为链表没有随机访问能力你不能直接跳到某个位置去比较。所以这道题的本质是考察你如何在链表的限制下用指针和反转操作去模拟“从两端往中间比较”的过程。这道题适合谁来刷在职准备面试的、在校刷题找工作的、想巩固链表基本功的人都应该把它吃透。它的经典程度不亚于“反转链表”和“合并两个有序链表”因为这三道题构成了链表操作的基本功三角。你能在白板上把这题写对、写快、写出最优空间复杂度面试官对你的链表功底基本是放心的。再说说这道题的几个进阶变体。有些面试官会让你不修改链表结构就判断回文这就要用到递归法或者把链表转成数组来做还有些面试官会先用数组版本热身再让你上链表版本。这些变体我在后面的章节里都会展开讲。2. 解法路径对比——从最笨到最优2.1 解法一复制到数组再双指针最直观的思路就是把链表上的所有节点值复制到一个数组里然后在数组上跑标准回文判断。这个解法思路极其简单代码也不容易出错时间复杂度O(n)空间复杂度O(n)。public boolean isPalindrome(ListNode head) { ListInteger list new ArrayList(); ListNode cur head; while (cur ! null) { list.add(cur.val); cur cur.next; } int left 0, right list.size() - 1; while (left right) { if (!list.get(left).equals(list.get(right))) { return false; } left; right--; } return true; }这题选Java做的话必须注意一点数组里存的是Integer对象比较要用equals不要用。因为Integer在-128到127之间有缓存如果你把两个超过127的数字放进数组再判断用会得到错误结果。这是我见过最多次的翻车现场真不是开玩笑。这个解法的优点是简单、稳、不依赖链表的任何特殊操作缺点是空间复杂度不够理想。面试官问到你接下来能不能优化空间你如果说不能印象分会打折。所以它适合作为热身解法用来确认你对题目的理解但绝不是最终答案。2.2 解法二快慢指针找中点加反转后半链表这个解法的思路就优雅多了也是大多数题解和面试官期待的标准答案。整体分三步走先用快慢指针找到链表的中间节点然后把中间节点之后的链表反转最后从头节点和反转后的链表头同时出发逐节点比较。为什么这样可行因为回文链表的结构是对称的前半段和后半段反着读相等。如果我们把后半段反转它就变成了和前半段方向一致的一串节点这时候从头往尾比较就能完成判断不需要从尾往前倒着走绕开链表不能反向遍历的天然缺陷。我自己第一次看到这个解法的时候最困惑的点是怎么保证快慢指针恰好找到的是正确的那一半的分界点这个细节我在下一节会专门讲清楚。这种解法的空间复杂度是O(1)因为只用了几个指针没有额外的容器。时间复杂度还是O(n)。在面试中能做到时间O(n)且空间O(1)对于这道题来说就是最优解了。3. 关键代码实现与逐步拆解3.1 快慢指针找中点的细节快慢指针找中点是一个很通用的技巧慢指针每次走一步快指针每次走两步。当快指针走到链表末尾时慢指针正好在中点附近。但这里有几个边界情况必须想清楚。链表的节点个数是奇数时比如1 - 2 - 3 - 2 - 1慢指针会停在3这个位置也就是正中间的那个节点。而反转后半段时应该从3的下一个节点开始反转也就是把 2 - 1 反转成 1 - 2。为什么因为3本身不需要参与比较它是中心的那个对称轴和谁比都不需要所以直接跳过它。链表的节点个数是偶数时比如1 - 2 - 2 - 1慢指针会停在第二个2的位置也就是右半段的起点这时候从慢指针开始反转正好。这两种情况可以用同一个代码逻辑兼容吗可以。关键在于快指针停止的条件。我们用的是 fast ! null fast.next ! null 这个条件它能让慢指针在奇数个节点时停在正中间、在偶数个节点时停在右半段的开头。ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }这四行代码看起来很短但逻辑密度很高。如果快指针移动时不小心用了 fast.next ! null fast.next.next ! null 作为条件结果就会不同因为快指针会少走一步慢指针在偶数情况下会落在左半段的末尾。这就导致后续反转的起点错误比较也会出错。3.2 链表反转的写法与常见错误反转链表是这道题的另一半而且是最容易出bug的地方。写反转链表时我建议用最经典的三指针法prev、cur、next。初始时prev指向nullcur指向要反转的第一个节点每次循环先把cur.next暂存到next再把cur.next指向prev然后prev和cur各前进一步。ListNode prev null; ListNode cur head; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; }这段代码结束之后prev就是反转后的新头节点。很多人写反转链表的时候会漏掉暂存next这一行直接写cur.next prev然后cur cur.next结果发现cur已经指向prev了链表后面全丢了。还有一点要注意如果这道题要求你判断完回文之后把链表恢复原状有些面试官会加这个要求那就需要在反转之前把后半段的起始节点记下来比较完之后再反转回去最后接上后半段。这个操作不复杂但很少有人会主动做面试时如果面试官提了你能做出来是明显的加分项。3.3 完整代码与逐行注释下面给出我在实际刷题时最终采用的一版完整代码我把它放在LeetCode上是可以直接提交通过的。我把它写得清晰优先不追求极端简洁因为面试时你更需要的是让面试官看懂你的思路。public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } // 第一步快慢指针找中点 ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 第二步反转后半段 ListNode secondHalfStart slow; if (fast ! null) { // 奇数个节点slow位于正中间需要反转的是slow后面的部分 secondHalfStart slow.next; } ListNode prev null; ListNode cur secondHalfStart; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; } // 第三步依次比较 ListNode p1 head; ListNode p2 prev; while (p2 ! null) { if (p1.val ! p2.val) { return false; } p1 p1.next; p2 p2.next; } return true; }这段代码里我做了个处理偶数个节点时slow恰好指向右半段的第一个节点所以secondHalfStart slow即可奇数个节点时slow指向中间的对称轴节点需要从slow.next开始反转。判断奇偶用的是fast是否为null快指针走到头的时候如果fast null说明是偶数个节点fast.next null说明是奇数个节点。这里不用重新遍历链表省了很多事。有同学可能会问快慢指针走完之后fast到底指向什么我们来看1 - 2 - 3 - 2 - 1五个节点。快指针从1开始第一步到3第二步到1此时fast.next null循环停止fast指向最后一个节点。如果是六个节点1 - 2 - 3 - 4 - 3 - 2快指针走到最后是null因为每次走两步最后刚好越过末尾。所以fast null对应偶数个节点fast.next null对应奇数个节点这个判断是可靠的。另一种写法是把奇数情况的处理统一到判断里比如第二步反转时不判断奇偶而是用停止条件控制。我看到很多题解是这么写的ListNode secondHalfStart slow.next; if (fast null) { secondHalfStart slow; }这两种写法都可以但我不推荐这种因为优先考虑slow.next会让阅读代码的人以为一定从slow.next开始碰到偶数情况反而不直观。按我上面的写法先判断奇偶再决定起点逻辑更顺。4. 常见问题与排查技巧实录4.1 边界条件的坑这道题边界条件非常容易翻车我把最常见的几个情况列出来。第一个是空链表和单节点链表。很多人一上来就写快慢指针没对这两个情况做特殊处理。空链表是回文数学上认为空串是回文单节点更是回文。我的代码开头直接if (head null || head.next null) return true把这个情况先兜住。第二个是两个节点的链表比如1 - 1。快慢指针走一轮slow停在第二个节点fast已经是null了偶数情况。然后反转从slow开始反转完还是那一个节点。比较时p1指向第一个节点p2指向第二个节点值相等返回true。这个过程看起来没问题但如果你把奇数偶数判断写反了就会出错。第三个是循环依赖问题。如果你在找中点的时候不小心让slow和fast互相引用或者在反转的时候没有正确断开原链表的连接比较的时候就会陷入死循环。我调试过几次这样的问题经验是每执行完一个步骤可以在纸上画一下链表当前的形状把各个指针指的位置标出来再对照代码走一遍基本都能找到问题。4.2 比较时的指针移动陷阱比较阶段有个很容易忽略的问题你反转的后半段是原链表的后半段但反转之后最后一个节点的next会变成null所以p2走到null时循环结束。这个设计没问题。但如果你在原链表上做反转时没有把slow.next后面的部分和前面断开比如奇数个节点时中间节点3的next还指向原链表后面的2反转后变成3 - null原来的链表结构就乱了。所以比较的时候要小心必须用反转后的头节点和原head开始比较循环条件是p2 ! null。如果你用p1 ! p2或者p1 ! null之类的条件在奇数节点的情况下会越界。我自己常用的一个调试小技巧是在比较之前输出一遍p1和p2的所有节点值肉眼确认一下反转是否正确。比如链表1 - 2 - 3 - 2 - 1反转后半段后p1是1 2 3p2是1 2从两边向中间比较刚好覆盖所有对称节点。这时候输出结果很容易发现到底是反转错了还是比较条件错了。4.3 关于是否恢复原链表的争论LeetCode上这道题的标准答案是不需要恢复链表因为函数结束后链表结构无关紧要。但在实际面试中不同的面试官对此有不同的要求。我在面某家公司的时候面试官在我写完代码后问你修改了链表的next指针如果这个链表后续还要使用怎么办我当时直接说可以恢复然后写了几行代码把后半段反转回来再拼回去。面试官点了点头。所以我的建议是练题阶段就把恢复链表的代码也写好面试时看情况使用。恢复的代码不复杂就是在比较结束后把p2所在的那一段再次反转然后让慢指针节点的next指向它。// 比较完之后恢复链表 ListNode secondHalfHead prev; ListNode cur2 secondHalfHead; prev null; while (cur2 ! null) { ListNode next cur2.next; cur2.next prev; prev cur2; cur2 next; } slow.next prev;这里注意如果链表是偶数个节点slow指向右半段的起始位置恢复后slow.next正好指向右半段的原始顺序如果是奇数个节点slow指向中间节点恢复后slow.next指向右半段的原始顺序。两种情况都正确。这个恢复过程不影响时间复杂度只是常数更大一些。5. 刷题策略与Hot 100的实际价值5.1 回文链表在热题100中的定位力扣热题100Hot 100可以说是刷题者的一份黄金清单它精选了各种算法类型中最具代表性的题目。回文链表在其中的地位属于“链表双指针”类别下的核心例题。和它并列的还有删除链表的倒数第N个节点、环形链表II等等。这几道题的共同点是都需要用双指针技巧在链表上做文章而且在面试中出现的频率都很高。如果你是一个准备找工作的同学我建议不要只盯着这一道题刷而是把热题100里链表相关的题目放在一起练比如两数相加、合并K个升序链表、反转链表II、排序链表、相交链表。这些题放在一起刷你会慢慢发现链表的操作套路其实就那么几种遍历、找中点、反转、合并、分离、成环判断。回文链表刚好把找中点和反转这两种基础操作串联在一起所以它对锻炼综合能力特别有价值。5.2 如何高效利用这道题提升代码能力刷这道题的时候我建议你做三个层次的练习。第一个层次不看任何提示自己独立写出能AC的代码目标是能过LeetCode的测试用例。第二个层次限定自己只能用O(1)空间复杂度的解法也就是快慢指针加反转看看能不能一遍写对。第三个层次思考如果这个链表是一个循环链表怎么办如果节点值不是int而是更复杂的对象怎么办如果要求原地修改并恢复怎么办。这种层层加码的练习方式比单纯刷完一遍就翻篇有效得多。我在刷题群里看到很多人刷这道题自己写一次没过就去看题解然后照着抄一遍就算过了。这样刷题效率太低。我的建议是先自己想想不出来可以看题解的第一段思路提示但代码一定要自己写。如果写完提交没过打印出中间过程对照测试用例手动推演。你亲手排查掉一个bug的记忆远胜于看十遍别人的正确代码。5.3 时间复杂度和空间复杂度的面试表述面试时很多人被问到复杂度分析就卡壳。这道题的准确表述是时间复杂度O(n)因为我们遍历链表两次一次找中点一次比较虽然反转过程也是O(n)但整体仍然是线性阶空间复杂度O(1)因为我们只使用了若干固定指针不随输入规模增长。有一个容易说错的细节有人觉得既然要反转链表那是不是要额外开辟n个节点的空间不是。我们是在原链表节点上改变指针方向没有new任何节点所以是O(1)。这一点我在面试中确认过很多次面试官听到这个回答会放心不少。6. 变形与扩展——从这道题延伸出去的思考这道题还有一种非常独特的解法思路递归。它的代码很简洁但理解起来需要一定的递归功底。思路是用一个全局的临时指针指向链表的头递归遍历到尾然后从尾到头一层层和临时指针指向的节点比较。这种方式本质上是用函数的调用栈来模拟从尾部向前访问链表的能力。private ListNode head; public boolean isPalindrome(ListNode node) { if (node null) { return true; } // 递归到最后一个节点 if (!isPalindrome(node.next)) { return false; } boolean check head.val node.val; head head.next; return check; }递归解法的时间复杂度还是O(n)但递归深度等于链表长度n所以隐含的空间复杂度是O(n)。这个解法在面试中可以作为备选展示但不推荐作为主要答案因为它有栈溢出的风险而且在工程中递归深度过深并不安全。再发散一下回文链表的判断方式和字符串回文的判断方式本质上一模一样。字符串可以用双指针从两端往中间走因为数组支持任意访问链表做不到所以我们必须先把后半段反转让链表在一端方向上具备“从尾往头读”的能力。这个思路在解决其他链表对称性问题时也很有用比如“判断两个链表是否形成回文序列”、“判断左右括号是否匹配的链表版”等类似场景。如果你已经能把这道题玩熟练了我建议继续刷这两道题巩固一个是“重排链表”143题它需要找中点、反转后半段、然后再交错合并把这道题的核心操作全组合了一遍另一个是“反转链表II”92题它对反转区间的控制要求更精细。刷完这三道你的链表基本功会非常扎实。可能有人会问工作里真的会用到这种技巧吗说实话日常业务开发中你很少会直接写一个快慢指针找链表中间节点。但这种思维方式的训练是真实有用的当你在数据流处理中需要快速找到中间位置的时候当你在设计缓存淘汰策略的时候当你在分析链表结构数据的对称性的时候这些基础操作就是你的心理工具箱。它们不会直接跳到你的代码里但它们塑造了你拆解问题的方式。