链表的回文结构，是算法刷题绕不开的一道经典题，题号 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) { vector<int> 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 -> 5，fast 最终停在 5（此时 fast->next 为 NULL），slow 停在 3，正是正中间那个节点。长度是偶数时，比如 1 -> 2 -> 3 -> 4，fast 最终走到 NULL，slow 停在 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 -> 3，rightHalf 的头就是原链表的倒数第一个节点。比较时 left 从 1 出发，right 从 1 出发：第一轮比 1 和 1，第二轮比 2 和 2，第三轮比 3 和 3，第三轮结束后 right 变成 NULL，循环终止，返回 true。注意第三轮比较的是"自己和自己"，而且这时候 left 已经越过中点、继续往原链表的右半段走了，但我们已经不需要再比下去了。为什么？因为后半段被反转后，右半段的所有节点都已经通过反转、以相反的顺序和左半段逐一配过对了；中点只是它自己和自己的镜像，比一次就够。甚至可以说，中点在这里起到了一个"无需对称搭档"的天然作用。偶数长度更直观。链表 1 -> 2 -> 2 -> 1，slow 指向第二个 2，反转 2 -> 1 得到 1 -> 2。比较：1 和 1，2 和 2，然后 right 走到 NULL，结束。左右两半严格一一对应，一个不多，一个不少。所以这个算法最巧妙的地方就是：根本不需要在代码里判断链表长度是奇是偶。快慢指针已经帮我们把"中点"选成了一个让后半段自动适配的位置，奇偶两种形态共用同一套逻辑，这比那种"先分奇偶讨论再分别处理"的写法优雅得多。4. 边界值、隐蔽坑位与我的排查思路4.1 空链表和单节点：最容易丢的特判很多版本的题面不会单独说明空链表怎么处理，但判题系统一定测到了。空链表没有节点，正着读、倒着读都是空，按惯例应该返回 true；单节点链表只有一个值，它和自己对称，也返回 true。如果没有这段特判，函数开头直接进快慢指针循环，空链表时 head 是 NULL，slow 和 fast 都指向 NULL，while (fast != NULL && fast->next != NULL) 这个条件会先检查 fast != NULL，发现是 NULL 直接短路，循环不会执行。看起来好像也没事？但是后面调用 reverse(slow) 时，传入 NULL，reverse 的 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 先走完变成 NULL，left 和 right 永远不可能相等，循环变成死循环。这是把数组的写法生搬硬套到链表上的典型翻车现场。第二个问题是反转函数里的多余操作。我一开始用了一个临时数组记录要反转的节点，再一个个重建，写出来又长又没有必要。后来想明白，反转只需要三个指针就够了，代码量直接少了一半。这讓我意识到，链表题的很多"看似高级"操作，拆到底就是指针的重新指向，能少开变量就少开变量。第三个问题最隐蔽：我在比较循环里提前 return false，导致链表后半段保持反转状态。测试某些用例时，如果判题系统把同一个函数循环调用，结构被改过的链表就会让下一次判断出错。改成"记录结果、循环结束再还原"之后，所有用例都稳了。这个问题在单次调用场景下暴露不出来，但确实是一个隐患，也让我记住了"函数退出前清理现场"的原则。6.2 给初学者的几条练习建议如果这篇文章能帮到你一点点，我最后再分享几条实操建议。第一，拿到链表题，先别急着写代码，拿一支笔画一下。奇数长度、偶数长度各画一个例子，把快慢指针每一步的位置标出来，比对着屏幕干想高效得多。第二，反转链表这种基础操作，建议单独练到闭着眼都能写对的程度，它出现的频率实在太高了，回文、重排、两数相加，全是它的变体。第三，写完之后，至少手工验证这几类用例：空链表、单节点、两个相同节点、两个不同节点、奇数回文、偶数回文、非回文。把这七个用例跑一遍，这道题基本就没有盲区了。第四，如果你使用的是 C 这类手动管理内存的语言，养成"所有提前返回路径都检查释放"的习惯，这类细节在真实项目和面试写码环节都会给你加分。回文结构这道题，表面上是判断对称，实际考察的是对链表单向遍历限制的理解，以及用指针操作化不可能为可能的能力。把这个题的"为什么"吃透了，后面碰到重排链表、旋转链表这一族题目，你会明显感觉轻松很多。
链表的回文结构，是算法刷题绕不开的一道经典题，题号 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) { vector<int> 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 -> 5，fast 最终停在 5（此时 fast->next 为 NULL），slow 停在 3，正是正中间那个节点。长度是偶数时，比如 1 -> 2 -> 3 -> 4，fast 最终走到 NULL，slow 停在 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 -> 3，rightHalf 的头就是原链表的倒数第一个节点。比较时 left 从 1 出发，right 从 1 出发：第一轮比 1 和 1，第二轮比 2 和 2，第三轮比 3 和 3，第三轮结束后 right 变成 NULL，循环终止，返回 true。注意第三轮比较的是"自己和自己"，而且这时候 left 已经越过中点、继续往原链表的右半段走了，但我们已经不需要再比下去了。为什么？因为后半段被反转后，右半段的所有节点都已经通过反转、以相反的顺序和左半段逐一配过对了；中点只是它自己和自己的镜像，比一次就够。甚至可以说，中点在这里起到了一个"无需对称搭档"的天然作用。偶数长度更直观。链表 1 -> 2 -> 2 -> 1，slow 指向第二个 2，反转 2 -> 1 得到 1 -> 2。比较：1 和 1，2 和 2，然后 right 走到 NULL，结束。左右两半严格一一对应，一个不多，一个不少。所以这个算法最巧妙的地方就是：根本不需要在代码里判断链表长度是奇是偶。快慢指针已经帮我们把"中点"选成了一个让后半段自动适配的位置，奇偶两种形态共用同一套逻辑，这比那种"先分奇偶讨论再分别处理"的写法优雅得多。4. 边界值、隐蔽坑位与我的排查思路4.1 空链表和单节点：最容易丢的特判很多版本的题面不会单独说明空链表怎么处理，但判题系统一定测到了。空链表没有节点，正着读、倒着读都是空，按惯例应该返回 true；单节点链表只有一个值，它和自己对称，也返回 true。如果没有这段特判，函数开头直接进快慢指针循环，空链表时 head 是 NULL，slow 和 fast 都指向 NULL，while (fast != NULL && fast->next != NULL) 这个条件会先检查 fast != NULL，发现是 NULL 直接短路，循环不会执行。看起来好像也没事？但是后面调用 reverse(slow) 时，传入 NULL，reverse 的 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 先走完变成 NULL，left 和 right 永远不可能相等，循环变成死循环。这是把数组的写法生搬硬套到链表上的典型翻车现场。第二个问题是反转函数里的多余操作。我一开始用了一个临时数组记录要反转的节点，再一个个重建，写出来又长又没有必要。后来想明白，反转只需要三个指针就够了，代码量直接少了一半。这讓我意识到，链表题的很多"看似高级"操作，拆到底就是指针的重新指向，能少开变量就少开变量。第三个问题最隐蔽：我在比较循环里提前 return false，导致链表后半段保持反转状态。测试某些用例时，如果判题系统把同一个函数循环调用，结构被改过的链表就会让下一次判断出错。改成"记录结果、循环结束再还原"之后，所有用例都稳了。这个问题在单次调用场景下暴露不出来，但确实是一个隐患，也让我记住了"函数退出前清理现场"的原则。6.2 给初学者的几条练习建议如果这篇文章能帮到你一点点，我最后再分享几条实操建议。第一，拿到链表题，先别急着写代码，拿一支笔画一下。奇数长度、偶数长度各画一个例子，把快慢指针每一步的位置标出来，比对着屏幕干想高效得多。第二，反转链表这种基础操作，建议单独练到闭着眼都能写对的程度，它出现的频率实在太高了，回文、重排、两数相加，全是它的变体。第三，写完之后，至少手工验证这几类用例：空链表、单节点、两个相同节点、两个不同节点、奇数回文、偶数回文、非回文。把这七个用例跑一遍，这道题基本就没有盲区了。第四，如果你使用的是 C 这类手动管理内存的语言，养成"所有提前返回路径都检查释放"的习惯，这类细节在真实项目和面试写码环节都会给你加分。回文结构这道题，表面上是判断对称，实际考察的是对链表单向遍历限制的理解，以及用指针操作化不可能为可能的能力。把这个题的"为什么"吃透了，后面碰到重排链表、旋转链表这一族题目，你会明显感觉轻松很多。