链表的回文结构是算法刷题绕不开的一道经典题题号 OR36 在不少在线题库的数据结构专项里都能看到。它要解决的问题一句话就能说清给定一个单链表判断从头到尾读和从尾到头读节点值序列是否完全一致。听起来简单但真正动手写的人都知道单链表这个结构本身就给回文判断添了不少麻烦——不能从后往前遍历没有随机访问长度还得自己数。这篇文章会从最朴素的数组解法讲起再重点拆解快慢指针加反转的标准解法把每一步的原理、每一处边界条件、每一个我踩过的坑都摊开讲。不管你是刚开始刷数据结构的新人还是准备面试想把经典题答出深度的人这篇都值得花十分钟读完。1. 先把题目翻译成人话回文结构对链表来说难在哪1.1 回文的基础定义与一个直觉例子回文这个词听起来挺学术其实意思非常朴素一个序列从头往后读和从尾往前读得到的内容完全一样。比如数字序列 1, 2, 3, 2, 1正着读是 1 2 3 2 1倒着读也是 1 2 3 2 1这就是回文。字符串里的 abcba、数字里的 12321都是同一个道理。链表的回文结构就是把这个概念搬到单链表上判断从链头到链尾的节点值序列是不是一个回文。比如 1 - 2 - 3 - 2 - 1 这条链表答案就是 true而 1 - 2 - 3 - 4 这种答案就是 false。题目编号 OR36在很多在线刷题平台的数据结构专项里都有属于不偏不怪的经典题。不少人第一次看到这道题脑子里第一个想法是这有什么难的我把它倒过来比一下不就行了。这个直觉是对的思路方向完全没毛病但真正动手写代码的时候单链表本身的结构限制会让你发现事情没那么简单。1.2 单链表的三重限制才是难点本体如果是数组或者字符串回文判断几乎不需要思考首尾各放一个指针往中间走逐个比较O(n) 时间、O(1) 空间就结束了。但单链表不一样它有三个让你没法抄数组答案的限制。第一没有随机访问。数组里可以用下标直接取 arr[i] 和 arr[n-1-i]链表的第 i 个节点只能从头一路 next 走过去想取尾部元素得先走到尾。第二不能从后往前遍历。单链表每个节点只有 next 指针没有 prev你拿到尾巴之后想往回收根本无路可退。第三没有一个天然的长度概念。数组有 n循环次数一目了然链表想数长度还得先遍历一遍而且遍历完一遍指针已经跑到尾部了。这三个限制叠加在一起导致最简单的双指针从两端往中间走的朴素方案在单链表上根本没法直接用。也正是这些限制决定了这道题的考察重点不是你会不会判断回文而是你怎么在一个只能前进不能后退的结构里完成对称比较。1.3 被很多人忽略的题目隐藏条件刷题最忌讳只盯着主流程题目里的隐藏条件往往是区分高分和及格分的关键。像 OR36 这道题藏得比较深的条件至少有这么几个。第一题面一般会明确要求或者隐含要求额外空间复杂度 O(1)。很多平台的版本会直接写出来请设计一个时间复杂度为 O(n)、额外空间复杂度为 O(1) 的算法。这说明你光写出一个能过的版本还不够还要思考怎么把辅助空间压下来。第二比较的是节点的值不是节点本身。两个节点的 val 相同就算匹配跟它们在内存里的地址无关——这听起来像废话但调试的时候很容易被为什么两个值明明一样却不相等这种假象带偏。第三输入可能给空链表。空链表没有任何节点算不算回文按惯例是算的因为空序列正着读倒着读一样。这个特判丢掉了很多在线判题系统会直接给你一个 WA。把这些条件梳理清楚再往下看解法你会发现所有实现细节其实都是在回应这些隐藏条件。2. 方案A复制到数组再用双指针正确但不够漂亮2.1 思路一句话降维成数组问题既然单链表的单向加无随机访问是主要障碍那么最直接的绕法就是把链表的值全部复制到一个数组里把链表问题降维成数组问题。数组可以随机访问首尾双指针随便走回文判断立刻变成 10 分钟就能写完的代码。具体的流程是第一次遍历链表数出节点个数分配一个长度相等的数组第二次遍历链表把每个节点的 val 依次填入数组最后在数组上用 left 和 right 两个下标从两端往中间比对。思路非常直白没有任何花哨。这种方案的计算量主要花在两次遍历和一次数组比对时间复杂度 O(n)代价是额外开了一个和链表等长的数组空间复杂度 O(n)。在只要求做出来的场景下它完全够用代码也几乎不可能写错。2.2 实现代码与写法细节如果用 C 语言写核心代码如下#include stdbool.h #include stdlib.h struct ListNode { int val; struct ListNode* next; }; bool isPalindrome(struct ListNode* head) { if (head NULL || head-next NULL) { return true; } // 第一遍遍历数长度 int len 0; struct ListNode* p head; while (p ! NULL) { len; p p-next; } // 分配数组并填入节点值 int* vals (int*)malloc(sizeof(int) * len); if (vals NULL) { return false; // 分配失败的保护性返回实际判题环境几乎不会触发 } p head; int i 0; while (p ! NULL) { vals[i] p-val; p p-next; } // 双指针从两端向中间比较 int left 0, right len - 1; while (left right) { if (vals[left] ! vals[right]) { free(vals); return false; } left; right--; } free(vals); return true; }这里有两个细节值得单独说明。第一个是 malloc 之后先判断是否为空。虽然刷题环境下内存分配失败的概率极低但这是一个好习惯真实工作里数组越界、内存泄漏这些问题都是在这种小地方积少成多的。第二个是在提前返回 false 的分支里记得 free(vals)。很多初学者在 main 流程里记得释放内存一走到提前 return 就忘了跑在线判题系统那种自动回收的判题器可能看不出来但在需要手动管理内存的环境里就是妥妥的泄漏。另外如果用的是 C 或 Java可以把数组换成 vector 或 ArrayList连长度都不用先数边遍历边 push_back 即可#include vector using namespace std; bool isPalindrome(ListNode* head) { vectorint vals; ListNode* p head; while (p ! NULL) { vals.push_back(p-val); p p-next; } int left 0, right vals.size() - 1; while (left right) { if (vals[left] ! vals[right--]) return false; } return true; }C 这版思路完全一样代码量还少了一大截。它和 C 版的本质区别在于C 需要手动管理数组C 的 vector 帮你把扩容和释放都藏起来了。2.3 为什么它能过但面试官不会满足我个人的看法是数组方案作为第一版答案是没问题的它能帮你快速确认题目理解没有偏差把主流程跑通。但如果在面试现场你只给出这一版大概率会收到追问能不能把空间复杂度降到 O(1)原因很简单。数组方案的空间是 O(n)它把链表的全部值复制了一份而额外空间 O(1)是这一类链表题里的高阶要求考察的是你对链表指针操作的掌控力。面试官想看到的不是你能借助随机访问结构绕开链表限制而是你能在链表本身的指针操作上完成对称比较。所以接下来这个方案才是这道题真正的主角。3. 方案B快慢指针定中点原地反转后半段这才是标准答案3.1 三步宏观流程先建立直觉回到最初的问题为什么单链表不能像数组一样从两端往中间比因为拿不到尾指针往前移动的能力。那我们换个思路——既然不能从尾部往回收能不能把后半段掉个头让后半段从尾到头的顺序变成从头到尾这样从两端往中间比就变成了两个从头部出发的指针同步往后走沿着这个思路最优解法可以拆成三步。第一步用快慢指针找到链表的中点把链表视觉上切成左右两半。第二步把从中间节点开始的后半段原地反转反转完的后半段头节点就相当于是原链表倒着看的第一个节点。第三步拿一个指针指向原链表头另一个指针指向反转后的后半段头两个指针同步向后移动、逐一比较值只要出现不相等直接返回 false右半边指针走完说明整条链表是回文。这三步连起来的核心思想是用反转这个操作把从尾部往前比较这个不可能的动作等价转换成了从新头部往后比较这个完全可行的动作。3.2 快慢指针找中点的原理与边界先写找中点的代码struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } // 循环结束后slow 指向的就是中点或右半段的起点这里面的逻辑其实是一个简单的追及问题。快指针一次走两步慢指针一次走一步当快指针到达链表尾部时快指针走的路程是慢指针的两倍所以慢指针恰好走了链表长度的一半也就是停在了中点附近。具体落在哪个节点取决于链表长度的奇偶。长度是奇数时比如 1 - 2 - 3 - 4 - 5fast 最终停在 5此时 fast-next 为 NULLslow 停在 3正是正中间那个节点。长度是偶数时比如 1 - 2 - 3 - 4fast 最终走到 NULLslow 停在 3也就是右半段的第一个节点。这个结果非常理想无论奇偶slow 指向的位置都恰好是反转后半段的起点。奇数时后半段是 3 - 4 - 5包含中点偶数时后半段是 3 - 4不包含多余节点。后面你会看到这样的起点选择让奇数、偶数两种情况可以用同一套代码统一处理。循环条件 while (fast fast-next) 是无数人写错过的地方。如果你写成 while (fast-next) 或者 while (fast-next-next)在某些长度下会提前结束或者访问空指针具体后果我放到下一部分专门讲。3.3 反转链表的图解式理解链表反转是比回文判断更基础的一道题这里直接给出迭代版本struct ListNode* reverse(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! NULL) { struct ListNode* next cur-next; // 先记住下一个节点 cur-next prev; // 当前节点掉头指向已经处理好的部分 prev cur; // prev 前移 cur next; // cur 前移 } return prev; // 循环结束时 prev 就是新链表的头 }用生活化的类比来说这就像你手里有一串珠子珠子之间用绳子拴住只能往一个方向穿。你要把整串珠子倒过来做法是解开第一颗珠子让它指向你手里已经整理好的反向串然后拿起第二颗重复同样的动作一边解一边搭等最后一颗珠子处理完你手上就是一串方向完全相反的新串。prev 变量始终指着已经整理好的反向串的头cur 是当前正要处理的珠子next 是防止珠子解开之后找不到后面部分的保险绳。这个写法里最容易漏的一行是循环开始前先把 cur-next 存到 next 里。如果漏了当你执行 cur-next prev 之后cur 原来的下一个节点就找不到了整个链表在第一次迭代就被斩断后面的节点全部丢失。3.4 完整代码与逐行注释把三块拼起来完整解决方案如下#include stdbool.h #include stdlib.h struct ListNode { int val; struct ListNode* next; }; // 反转以 head 为头节点的链表返回新链表的头节点 struct ListNode* reverse(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! NULL) { struct ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; } // 判断链表是否为回文结构 bool isPalindrome(struct ListNode* head) { if (head NULL || head-next NULL) { return true; } // 第一步快慢指针找中点 struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } // 第二步反转以 slow 为起点的后半段 struct ListNode* rightHalf reverse(slow); // 第三步双指针同步比较 struct ListNode* left head; struct ListNode* right rightHalf; while (right ! NULL) { if (left-val ! right-val) { return false; } left left-next; right right-next; } return true; }这个版本的时间复杂度是 O(n)找中点扫了大约 n/2 个节点反转扫了 n/2 个节点比较又扫了 n/2 个节点加起来还是 O(n)。额外空间只需要几个指针变量与链表长度无关所以是 O(1)。这正好命中题面时间 O(n)、额外空间 O(1)的核心要求。3.5 奇偶长度的统一处理关键点很多第一次看这个解法的人会卡在一个疑问奇数长度时中点那个节点也被反转进后半段了比较的时候它会不会被拿出来和自己比两次我们实际走一遍。链表 1 - 2 - 3 - 2 - 1快慢指针结束后 slow 指向 3。反转 3 - 2 - 1得到 1 - 2 - 3rightHalf 的头就是原链表的倒数第一个节点。比较时 left 从 1 出发right 从 1 出发第一轮比 1 和 1第二轮比 2 和 2第三轮比 3 和 3第三轮结束后 right 变成 NULL循环终止返回 true。注意第三轮比较的是自己和自己而且这时候 left 已经越过中点、继续往原链表的右半段走了但我们已经不需要再比下去了。为什么因为后半段被反转后右半段的所有节点都已经通过反转、以相反的顺序和左半段逐一配过对了中点只是它自己和自己的镜像比一次就够。甚至可以说中点在这里起到了一个无需对称搭档的天然作用。偶数长度更直观。链表 1 - 2 - 2 - 1slow 指向第二个 2反转 2 - 1 得到 1 - 2。比较1 和 12 和 2然后 right 走到 NULL结束。左右两半严格一一对应一个不多一个不少。所以这个算法最巧妙的地方就是根本不需要在代码里判断链表长度是奇是偶。快慢指针已经帮我们把中点选成了一个让后半段自动适配的位置奇偶两种形态共用同一套逻辑这比那种先分奇偶讨论再分别处理的写法优雅得多。4. 边界值、隐蔽坑位与我的排查思路4.1 空链表和单节点最容易丢的特判很多版本的题面不会单独说明空链表怎么处理但判题系统一定测到了。空链表没有节点正着读、倒着读都是空按惯例应该返回 true单节点链表只有一个值它和自己对称也返回 true。如果没有这段特判函数开头直接进快慢指针循环空链表时 head 是 NULLslow 和 fast 都指向 NULLwhile (fast ! NULL fast-next ! NULL) 这个条件会先检查 fast ! NULL发现是 NULL 直接短路循环不会执行。看起来好像也没事但是后面调用 reverse(slow) 时传入 NULLreverse 的 while (cur ! NULL) 不执行返回 NULL然后比较循环 while (right ! NULL) 也不执行最后返回 true。所以空链表误打误撞也对。但单节点链表呢head-next 是 NULL如果不特判快慢指针循环结束后 slow 还是 head反转 head 自己得到一个指向自身的单节点比较时 left 和 right 都指向同一个节点left-val right-val 成立返回 true。好像也对那是不是可以不写特判从结果看确实能蒙对但这种碰巧正确的代码非常危险它依赖了 reverse 对空链表和单节点天然友好的行为一旦你后面加了别的逻辑比如还要恢复链表没特判就会出问题。我建议老老实实加上if (head NULL || head-next NULL) return true;让代码的意图一目了然也让后续的指针操作建立在链表至少有两个节点的安全前提上。4.2 快慢指针循环条件写错会出什么事这个坑我见过不少人踩过包括我自己早期也踩过。主要有两种错误写法。错误写法一while (fast-next ! NULL)。只判断 fast 的下一个节点不判断 fast 本身。当快指针已经走到最后一个节点时fast-next 是 NULL循环正常结束但如果链表长度是偶数fast 会直接走到 NULL这时候再去访问 fast-next就是空指针解引用程序直接崩溃。判题系统里最常见的段错误Segmentation Fault就是这么来的。错误写法二while (fast ! NULL fast-next-next ! NULL)。这个写法前半段判断了 fast 非空后半段却又直接访问 fast-next-next假如 fast-next 本身就是 NULL一样崩。而且就算不崩这个条件会比标准写法提前一轮结束循环导致偶数长度时 slow 停的位置偏左一个节点后续反转的区间就多包含了一个左半段节点比较结果可能是错的。正确的写法就是while (fast ! NULL fast-next ! NULL)利用 的短路特性保证只有当 fast 和 fast-next 都非空时才允许访问 fast-next-next。这是快慢指针问题里的标准防护姿势建议直接形成肌肉记忆。4.3 比较循环的终止到底看哪边比较阶段判断循环是否结束有两种写法while (right ! NULL)或者while (left ! NULL right ! NULL)。两种都能通过判题但理解它们之间的细微差别是有价值的。我们只关心反转后的后半段是否被完整比对过而右半段的长度永远不会超过左半段。奇数长度时反转后的后半段包含中点长度是 n/2 向上取整而 left 从头部出发要走完这么多步左指针恰好停在原链表的中点之后的那个节点上。偶数长度时两者同步走到 NULL。因此用while (right ! NULL)作为终止条件语义最干净右半边比对完答案就已经确定不需要再检查 left 是否还有剩余。有些同学会担心万一 left 比 right 短怎么办这在当前算法里不可能发生因为反转的后半段起点就是中点或右半段起点它的长度最多等于左半段。理解这一点之后你会发现while (right ! NULL)不是少写了一个条件而是故意只保留了一个正确的条件。4.4 修改了原链表怎么优雅地还原这个解法有一个副作用它把原链表的后半段反转了函数返回之后链表已经不是最初的结构。判题系统只看返回值所以不影响 AC。但如果你在面试面试官很可能会追问一句你修改了输入数据这合适吗如果接口语义要求不能修改原始链表或者你希望代码更严谨可以在比较完成之后把后半段再反转一次恢复原状。关键点在于比较结束后rightHalf 依然指向反转后半段的头对它再调用一次 reverse得到的就是恢复原序的后半段整个链表就还原了。// reverse 函数复用前一节的实现 bool isPalindrome(struct ListNode* head) { if (head NULL || head-next NULL) return true; struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } struct ListNode* rightHalf reverse(slow); struct ListNode* left head; struct ListNode* right rightHalf; bool result true; while (right ! NULL) { if (left-val ! right-val) { result false; break; } left left-next; right right-next; } reverse(rightHalf); // 还原后半段 return result; }注意这里的改动原来发现第一个不匹配就 return false现在改成先记录结果、跳出循环确保无论结果如何都要执行最后的 reverse(rightHalf) 还原操作。这个延迟返回、先清理现场的思路在真实工程里也很常见函数退出前要保证资源或数据结构回到合理状态。5. 复杂度拆解与面试延伸空间O(1)的含金量在哪5.1 三种方案的复杂度对照为了让你对整道题有一个全局视角我把常见的三种解法放在一起对比。方案时间复杂度额外空间复杂度是否修改原链表代码难度数组法O(n)O(n)否低快慢指针反转O(n)O(1)是可恢复中递归法O(n)O(n)递归栈否中从表格可以直观看到数组法最稳但空间不够看递归法思路优雅空间却被调用栈拖累只有快慢指针反转同时满足时间 O(n) 和额外空间 O(1)。这也是为什么它成为标准答案。5.2 递归版与栈版为什么实际空间不算O(1)可能有同学会说递归不是也能做到不复制数组吗递归版的思路很巧妙先递归到链表的最后一个节点然后在递归返回的过程中用外部的一个指针从链表头部同步往后走实现一个指针从头往尾、一个指针从尾往头的对称比较。问题在于递归调用要深入 n 层每一层都需要在系统调用栈里保存现场这套开销的空间复杂度是 O(n)。题目里说的额外空间复杂度 O(1)不允许你借助递归栈这种隐式空间来规避。使用显式的栈来存前半段节点也是同理栈的空间同样是 O(n)。所以在严格的复杂度要求下这两种写法都不达标只能作为思路拓展来了解。5.3 面试官追问的几个变体问题面试官围绕这道题可以问出很多变体提前准备好这些延伸比多刷三道新题都值。变体一如果链表是双向链表回文判断怎么做双向链表有 prev 指针可以先遍历到尾然后头尾各一个指针往中间走。时间 O(n)、空间 O(1)实现比单链表简单得多。如果面试官这么问他多半是在确认你是否理解双向遍历能力对这道题的关键作用。变体二如果不允许修改原链表又要求 O(1) 空间怎么办那基本是无解的。理论上在不借助额外线性空间的前提下只读地判断单链表回文是不现实的——你没有一个合法的途径从尾部往前读取也没有额外空间记录已经读过的节点。诚实地说这种情况下没有 O(1) 空间的解法比硬编一个错误解法更显专业。变体三链表长度巨大比如上千万节点用什么方案这种规模下O(n) 的数组辅助空间可能直接导致内存不足反转加比较的 O(1) 方案就体现出实际价值。同时要注意链表过长时递归一定会爆栈所以递归版在这里也直接被淘汰。这是 O(1) 空间诉求的现实意义所在。变体四如果链表中存在环怎么处理回文结构通常默认链表无环。如果出现环应该先用判环算法快慢指针探测有环就不是一个严格的线性结构需要先做特殊处理。这个扩展属于加分项能答出来会显得你考虑周全。6. 复盘与实操心得从WA到AC我经历了什么6.1 一步步排查过程的真实故事我第一次写这道题的时候一上来就是数组法AC 之后觉得太没挑战于是决定挑战 O(1) 空间版本。结果连着交了几次全是 WA当时对着一屏错误用例查了很久最后发现了几处很有意思的问题。第一个问题出在数组法思维惯性上。数组法比较时left 和 right 从两端向中间走终止条件是 left right。我照着这个思路写链表版把终止条件写成while (left ! right)结果在奇数长度时right 先走完变成 NULLleft 和 right 永远不可能相等循环变成死循环。这是把数组的写法生搬硬套到链表上的典型翻车现场。第二个问题是反转函数里的多余操作。我一开始用了一个临时数组记录要反转的节点再一个个重建写出来又长又没有必要。后来想明白反转只需要三个指针就够了代码量直接少了一半。这讓我意识到链表题的很多看似高级操作拆到底就是指针的重新指向能少开变量就少开变量。第三个问题最隐蔽我在比较循环里提前 return false导致链表后半段保持反转状态。测试某些用例时如果判题系统把同一个函数循环调用结构被改过的链表就会让下一次判断出错。改成记录结果、循环结束再还原之后所有用例都稳了。这个问题在单次调用场景下暴露不出来但确实是一个隐患也让我记住了函数退出前清理现场的原则。6.2 给初学者的几条练习建议如果这篇文章能帮到你一点点我最后再分享几条实操建议。第一拿到链表题先别急着写代码拿一支笔画一下。奇数长度、偶数长度各画一个例子把快慢指针每一步的位置标出来比对着屏幕干想高效得多。第二反转链表这种基础操作建议单独练到闭着眼都能写对的程度它出现的频率实在太高了回文、重排、两数相加全是它的变体。第三写完之后至少手工验证这几类用例空链表、单节点、两个相同节点、两个不同节点、奇数回文、偶数回文、非回文。把这七个用例跑一遍这道题基本就没有盲区了。第四如果你使用的是 C 这类手动管理内存的语言养成所有提前返回路径都检查释放的习惯这类细节在真实项目和面试写码环节都会给你加分。回文结构这道题表面上是判断对称实际考察的是对链表单向遍历限制的理解以及用指针操作化不可能为可能的能力。把这个题的为什么吃透了后面碰到重排链表、旋转链表这一族题目你会明显感觉轻松很多。