链表的回文结构这道题我在不少场合提过它是链表操作里基本功的集大成者。判断一个序列是不是回文放到数组里是送分题但一旦装进单向链表不能随机访问、不能从后往前遍历难度就上来了。OR36这道题正是把找中点反转链表同时遍历比较三个技能揉在一起考察你对指针操作的熟练度和边界条件的敏感度。这篇就是我对这题的完整复盘从题意拆解到代码实现再到刷题时反复踩的坑一次说清楚。这道题适合正在准备求职笔试、考研机试的同学也适合学完链表但想检验自己指针功底是否扎实的人。如果你已经能独立写出正确代码我后面关于边界条件和链表修改副作用的分析依然值得看一看。1. 先把题目看懂回文结构到底在考什么1.1 题目描述与输入输出题目要求判断一个单链表是否为回文结构。所谓回文就是正着读和倒着读一样。比如1 - 2 - 2 - 1是回文1 - 2 - 3不是空链表和只有一个节点的链表按约定也算回文。链表定义通常是这样的struct ListNode { int val; struct ListNode *next; };函数签名是bool isPalindrome(struct ListNode* head)返回true或false。到这步还没有难度可言。真正的难点在于单向链表只能从前向后走你没法直接拿到最后一个节点和第一个节点比较。所以核心挑战就是——如何在不能反向遍历的前提下完成头尾逐对比较这个动作。1.2 这道题的经典之处这道题在多个在线评测平台都有收录OR36是其中一个编号。它之所以常见是因为它把链表题最常考的两项基础能力叠在了一起快慢指针找中点和反转链表。这两个技能单独出题时大家都会写但组合起来很多人的代码就开始出现各种边界错误。拿真实刷题场景来说某公司的一道面试题就是这道原题面试官要求不借助额外存储空间完成。这意味着你不能把链表节点值复制到数组里判断。我见过不少候选人能说出快慢指针反转后半段的思路但写代码时要么快指针移动条件写错导致空指针要么反转后链表被断开要么完全没考虑节点个数的奇偶差异。这些都是这题真正的考点。2. 解题思路从最直观的方案到最优解2.1 方案A辅助数组先能过再优化最容易想到的办法是遍历链表把所有节点的值存进一个数组然后用双指针从数组两端向中间夹逼。长度为 n数组下标 i 和 n-1-i 对应的值应当相等。bool isPalindrome(struct ListNode* head) { int arr[100005]; int len 0; struct ListNode* cur head; while (cur) { arr[len] cur-val; cur cur-next; } int left 0, right len - 1; while (left right) { if (arr[left] ! arr[right]) return false; left; right--; } return true; }这个方案的时间复杂度 O(n)、空间复杂度 O(n)。在牛客上通常也能通过因为题目没卡空间。但它有个问题如果面试官追问如何做到空间 O(1)只写出数组方案是不够的。另外如果链表长度达到十万级在栈上开一个很大的数组也可能出问题。所以这个方案适合用来确认理解题意、梳理思路但不该是最终答案。2.2 方案B快慢指针定位中点 反转后半段这是标准的 O(1) 空间解法。思路分三步用快慢指针找到链表中点。慢指针每次走一步快指针每次走两步。快指针走到末尾时慢指针刚好在中点。把中点之后的那段链表反转。用两个指针一个从头部走一个从反转后的尾部走逐个比较节点值。如果全相等就是回文。为什么快慢指针能找到中点你想象两个人跑步A的速度是B的两倍。A到达终点时B正好在跑道的中间。链表中快指针走两步、慢指针走一步同理。这个思想在环形链表检测、找倒数第K个节点里都会出现值得单独理解透。2.3 为什么最终选方案B核心原因是空间 O(1)。它不需要任何额外数组只用了几个指针变量。对于链表回文这种问题快慢指针 反转已经是社区公认的最优套路。另外这道题本身还隐含一个考点反转链表这个操作本身要写得对。很多人的快慢指针逻辑没问题但反转函数对空指针的处理不到位导致整个程序崩溃。方案B强制你同时掌握两个基础操作用它作为最终方案本身就是一次完整的训练。3. 完整代码实现与逐段拆解3.1 找中点的细节奇偶链长的差异找中点这一步看似简单代码里藏着一个大坑链表长度是奇数还是偶数慢指针最终停的位置不同。先看代码struct ListNode* getMiddle(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }当链表有 5 个节点时奇数fast 初始在 1移动两次后 fast 到 5slow 到 3循环条件是fast fast-next。当 fast 在 5 时fast-next为空循环停slow 停在 3正好是中点。当链表有 4 个节点时偶数fast 移动一次到 3slow 到 2再移动一次 fast 到 NULLslow 到 3。注意偶数长度时slow 停在中点的后一个节点也就是第 3 个节点而不是第 2 个。这直接影响后面反转的起点选择。为什么偶数时 slow 不停在 2因为快指针走完时是 NULL慢指针没法知道自己应该停在两个中点的前一个。这是快慢指针找中点的固有行为。我们的处理方式很直接从 slow 开始反转后半段。比如1 - 2 - 3 - 4 - NULLslow 停在 3反转3 - 4变成4 - 3然后从头指针 head1和反转后的头4开始比较1和4不等返回 false。正确。再比如1 - 2 - 2 - 1 - NULLslow 停在第三个节点 2 的位置反转后变成1 - 2原链表后半段是2 - 1反转后头变成了原来的最后一个节点 1。注意这里我表述容易乱直接看代码原链表是1(第一个) - 2(第二个) - 2(第三个) - 1(第四个)slow 在第三个节点值为2。反转从第三个节点开始的链表也就是反转2(第三个) - 1(第四个)得到1(第四个) - 2(第三个)。然后从 head值为1和这个新链表头值为1开始比较。依次比较11接着第二个节点值为2和新链表的下一个节点值为2比较相等。结果是 true。逻辑成立。3.2 反转链表的实现要点反转单链表用迭代法三指针维护。核心逻辑是不断把当前节点的 next 指向前一个节点struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur) { struct ListNode* nextNode cur-next; cur-next prev; prev cur; cur nextNode; } return prev; }这里有个细节反转过程中用nextNode暂存cur-next否则你改了cur-next之后就找不到原来的下一个节点了。这个操作本身没什么难度但它是整个方案里最容易写错的一环。尤其是当head为 NULL 时反转函数要能直接返回 NULL上面的代码天然满足。3.3 把三步拼起来主函数逻辑bool isPalindrome(struct ListNode* head) { if (head NULL || head-next NULL) { return true; } struct ListNode* mid getMiddle(head); struct ListNode* rightHead reverseList(mid); struct ListNode* left head; struct ListNode* right rightHead; while (right) { if (left-val ! right-val) { return false; } left left-next; right right-next; } return true; }注意比较循环的条件用while (right)而不是while (left right)。为什么因为 right 是从后半段反转来的它最长和 left 等长。当链表长度为奇数时后半段比前半段少一个节点中点被归入了后半段但比较时 right 走到中点时会和 left 在中点相遇比较完成后 right 变成 NULL循环自然结束。用right作为循环条件天然处理了奇偶差异不会出现空指针解引用。我最初写的时候用的是while (left right)代码也能跑通但逻辑上不如while (right)干净。这是我在实际写代码中调整过的一个细节。3.4 复杂度分析与一个小隐患时间上找中点走一遍链表 O(n)反转后半段走一遍 O(n/2)比较再走一遍 O(n/2)总复杂度 O(n)。空间上只有若干指针O(1)。但这里有个隐藏问题原链表被修改了。后半段被反转后链表结构不再是原来的样子。如果题目只要求返回 bool这没有问题。但如果调用方期望链表保持不变这么做就可能被扣分。部分严格的环境还会在函数返回后检查链表是否被改动。为了稳妥可以在比较完成后把后半段再反转回来恢复原链表结构。这个操作需要你在比较前保存好rightHead比较结束后对rightHead再调用一次reverseList重新接到mid后面。代码可以这样改bool isPalindromeAndRestore(struct ListNode* head) { // ... 前面的判断一样 struct ListNode* mid getMiddle(head); struct ListNode* rightHead reverseList(mid); struct ListNode* left head; struct ListNode* right rightHead; bool result true; while (right) { if (left-val ! right-val) { result false; break; } left left-next; right right-next; } // 恢复链表 mid-next reverseList(rightHead); return result; }我在实际刷题时很少写恢复版本因为在线评测只关心返回值。但在面试场景中主动提到修改了链表如果需要我可以恢复原结构会显得你考虑问题更全面。4. 实操中的坑编译不过、边界错、超时4.1 高频错误1空指针崩溃最常见的报错是运行时访问空节点的 next。典型错误写法是把快慢指针循环写成while (fast-next fast-next-next)。当链表只有 2 个节点时fast初始在第一个节点fast-next存在fast-next-next是 NULL循环条件为假slow 停在第一个节点看起来没错。但当链表只有 1 个节点时fast-next本身就是 NULL你访问fast-next-next就会崩溃。所以循环条件必须写成while (fast fast-next)先保证 fast 本身非空再访问fast-next。另一种空指针场景在比较阶段。如果你把循环条件写成while (left right)然后循环体里left left-next可能把 left 变成 NULL下一轮循环还能正常结束倒是不会崩。但如果你在循环条件里多写一步right-next就可能崩。我的建议是在任何解引用节点的代码前先问自己一句这个指针当前一定非空吗。4.2 高频错误2偶数长度的中点定位偏差有些写法会在快慢指针结束后对偶数长度做特殊处理比如让慢指针回退一步。这倒不是不行但容易引入新的 bug。从实践来看不需要做奇偶判断让 slow 停在偶数情况下的后一个中点直接从那里反转后半段比较逻辑用while (right)就能兼容所有情况。如果你非要在偶数时让 slow 停在前一个中点那反转的范围就得多包含一个节点比较逻辑也要相应改变反而复杂。我见过不少人在这上面绕了半天其实就是没有用允许中点偏后的思路。4.3 高频错误3反转后链表断裂反转后半段时如果反转函数起点传错了节点可能导致整个链表被拆成两段。比如有的写法想反转中点之后的部分于是找中点后取mid-next作为反转起点结果原链表从中点处断开前半段和后半段失去联系。这本身不影响比较因为你的比较是从 head 和反转后的头开始的前半段不需要通过 next 连到后半段。但如果你后续想恢复链表就会因为断链而无从恢复。我的建议是反转整个从 slow 开始的子链表包括 slow 本身。这样虽然把中点也反转了但比较时不会出错恢复时也更容易把反转后的链表直接接到 mid 后面。4.4 排查与自测清单调试链表题最直接的办法是写一个打印链表函数void printList(struct ListNode* head) { while (head) { printf(%d - , head-val); head head-next; } printf(NULL\n); }在找完中点、反转完链表后分别打印确认每一步结果符合预期。这里我给出一份自测用例清单你可以逐个验证测试用例预期结果说明NULLtrue空链表单个节点 1true单节点1-2false偶数长度非回文1-1true偶数长度回文1-2-1true奇数长度回文1-2-3false奇数长度非回文1-2-2-1true标准偶数回文1-2-3-2-1true标准奇数回文2-1-3-1-2false偶数值相同但顺序不对4.5 关于原地修改链表的取舍如果题目明确说不能修改链表那答案要换一种写法。可以在找中点后不反转后半段而是用递归栈反向比较但递归深度等于链表长度的一半本质上空间复杂度还是 O(n)只是不显式用数组而已。所以我认为这类题的合理默认答案仍然是快慢指针 反转但你要在描述方案时主动说明我需要反转后半段这会临时修改链表结构。实际面试中这个说明本身就能加分。我记得有一次模拟面试候选人用了反转法我追问如果调用方不能接受链表被修改呢他没答上来。后来我建议他补一句可以再反转回来他立刻就明白了。这个小技巧也分享给你。5. 举一反三从这题延伸出去的技能5.1 快慢指针是一个通用工具箱快慢指针不止能找中点。判断链表是否有环用快慢指针一个走两步一个走一步如果相遇说明有环找倒数第 K 个节点让一个指针先走 K 步然后两个指针同步走前面的指针到达末尾时后面的指针正好在倒数第 K 个节点。这两个场景在面试中出现频率极高。所以做 OR36 这题时不要只背代码要把快慢指针当作一个独立技能模块拆出来理解。它的本质是利用速度差制造位置差从而在单次遍历中获取链表里的特定位置信息。5.2 反转链表是另一块基石反转链表本身单独就是一道经典题有迭代和递归两种写法。OR36 里用的是迭代法原因很明确递归反转在链表很长时会占用 O(n) 的调用栈空间违背了空间 O(1) 的最优目标。如果你对递归反转有兴趣可以额外练习一下但面试时写迭代法理由就是空间效率更高也更不容易在边界情况下出错。5.3 变式题与进阶方向判断回文链表但不允许修改链表结构可以先用快慢指针找中点然后原地反转后半段做比较比较完再反转回来总时间不变结构不变。如果是双向链表判断回文直接从 head 和 tail 两个方向夹逼比单链表简单很多但也正因如此考察价值不高。如果链表节点值不是整数而是字符串比较用strcmp其余逻辑不变。刷完这题建议紧接着刷两个配套题环形链表和反转链表把这两个技能夯实。技能树打通之后回头再看 OR36你会发现它其实就是一个把两个基础技能拼装起来的应用题。我个人在实际刷题过程中的一个小经验是链表题先别急着写代码拿支笔画一下指针的移动过程。把节点画成方框指针画成箭头手动模拟两个用例一个奇数长度、一个偶数长度代码自然就有思路了。这个习惯帮我少踩了很多空指针的坑。另外写代码时保持一个习惯凡是解引用p-next之前先想一遍p是否可能为 NULL。不要觉得这是小题大做链表题的崩溃九成发生在这一瞬间。把这个习惯刻进肌肉记忆你会发现所有链表题的正确率都会明显提高。
