企业官网建设流程全解析

链表回文这种题，说实话算是链表操作里的“分水岭”。OR36这道题，刷题平台上的题号记不太清，但内容我闭着眼都能画出来：给一条单链表，判断它是不是回文结构，就是说链表的节点值序列从左往右读和从右往左读是否完全一致。比如 1->2->3->2->1 就是回文，1->2->2->1 也是回文，而 1->2->3->1 就不是。很多新手第一次看到这题，第一反应就是“这不简单嘛，转成数组再用双指针从两头往中间比”。能这么做，但面试官大概率会追问一句：“能不能优化到 O(1) 的空间复杂度？”这个时候，如果你只会数组法，基本就卡住了。

这篇文章不打算给你灌鸡汤，就老老实实把这道题从暴力到最优全部拆开：数组法、递归法、快慢指针 + 反转后半段的最优解，每一段代码都给你，每一步为什么这么写、坑在哪儿，也都讲明白。不管你是刚开始刷链表题的小白，还是准备面试想把手撕算法练熟的选手，这篇都值得看完。尤其是那些“看似对了、一跑就崩”的边界条件，我会全部摊开来聊。

1. 题解核心思路拆解

1.1 回文链表到底在考什么

回文（Palindrome）这个概念大家不陌生，字符串、数组里判断回文非常简单：左右两个指针往中间走，逐个比较就行。但换到链表上，问题就来了。单链表是单向的，只能从头往后遍历，你没办法像数组那样随机访问“倒数第几个节点”。所以这道题表面上问的是“是不是回文”，实际上考的是三个链表的底层基本功：

• 怎么在单链表中找到中间节点？
• 怎么把一条链表原地反转？
• 怎么处理奇偶长度带来的边界值差异？

这三个点恰好覆盖了链表操作里最常见、最核心的技法。所以这道题才被很多面试官当成“试金石”题——代码量不大，但考察点不少，写得干净利落的人，基本功基本不会差。

1.2 从回文定义反推设计思路

回文的本质是：前半段与后半段“逆序后”相等。比如长度为 5 的链表 1->2->3->2->1，前半段是 1、2，后半段是 2、1，把后半段反转后就是 1、2，正好和前半段相等。中间那个 3 是“中心”，不需要参与比较。

想通这一点，解决方案就呼之欲出：

1. 先找到链表的中点；
2. 把中点之后的节点整体反转；
3. 用两个指针，一个从正数第一个节点走，一个从原链表尾节点（反转后的新头）走，逐个比较；
4. 如果比到最后都相等，就是回文，否则不是。

这就是最优解的核心脉络。后面的所有代码，都是围绕这条主线展开的。

1.3 为什么首选快慢指针而不是先求链表长度

有人可能会想：既然要找中点，我直接先遍历一遍求出链表长度 n，然后走 n/2 步找到中点不就行了吗？确实可以，时间复杂度也是 O(n)，代码写起来甚至更直观。但在链表题里，快慢指针是更高频、更通用的技巧。它的优势在于：

• 只遍历一遍就能找到中点；
• 不需要额外维护“长度”这个变量；
• 处理环形链表、找倒数第 k 个节点等场景时，同样适用。

当然，面试的时候如果你先讲求长度法，再讲优化成快慢指针，这个思路推进过程本身也是加分项。但最终给出的最优解，一定是快慢指针。

1.4 先想清楚空间复杂度的取舍

这道题最容易被诟病的就是“用数组存值”。数组法的空间复杂度是 O(n)，在数据量小的测试用例下看不出问题，可一旦链表长度来到百万级，额外分配一个百万长度的数组，既不优雅也不靠谱。递归法虽然代码很漂亮，但递归栈深度等链表长度，依然是 O(n) 空间，长链表还可能栈溢出。真正能达到 O(1) 空间的，只有“反转后半段 + 双指针比较”这种做法。

所以在正式讲代码前，你要有一个意识：解链表题和做业务需求一样，先看限制条件最严的场景。如果题目没有明确说不能改链表结构，那么反转后半段是性价比最高的选择。

2. 从暴破到最优：三种解法逐个拆解

2.1 解法一：复制到数组，双指针往中间扫

这个方法最直白。第一次遍历链表，把所有节点的值按顺序塞进一个数组；然后用数组双指针，一头一尾往中间比较。

核心代码大概是这样的（以 C++ 为例）：

bool isPalindromeByArray(ListNode* head) { vector<int> vals; ListNode* p = head; while (p != nullptr) { 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; } ++left; --right; } return true; }

这个解法的优势非常明显：简单、不容易出错，基本不需要考虑链表指针细节。缺点也很明显：如果链表特别长，数组会占用大量额外空间；而且在某些面试场景下，面试官会直接追加一句“不能用额外容器”，那这个方法就彻底废了。

需要强调的是，这并不代表它“不好”。对于实际业务里那些长度可控、又不要求极低内存的场景，数组解法足够可靠。刷题和面试，你得学会在不同条件下切换思路。

2.2 解法二：递归后序遍历模拟双端比较

递归解法的思路非常巧妙：链表天然是线性的，所以我可以先递归到最后一个节点，然后在“回溯”的过程中，让一个“外部指针”从头开始往前走，这样一前一后就能进行比较。

举个例子，链表是 1->2->3->2->1，递归函数一层层深入：

1. 递归到节点 5（值 1），回溯到它时，外部指针指向节点 1（值 1），比较相等，外部指针后移；
2. 继续回溯到节点 4（值 2），此时外部指针指向节点 2（值 2），比较相等；
3. 继续回溯到节点 3（值 3），外部指针指向节点 3（值 3），相等；
4. 之后所有回溯节点都比较完毕，返回 true。

C++ 代码一般写成这样：

class Solution { private: ListNode* front; public: bool check(ListNode* node) { if (node == nullptr) { return true; } bool result = check(node->next); // 后半部分比较已经失败的话，直接短路 result = result && (front->val == node->val); front = front->next; return result; } bool isPalindromeByRecursion(ListNode* head) { front = head; return check(head); } };

这个解法的代码非常短，但有两个致命短板：

• 递归深度等于链表长度，空间复杂度是 O(n)；
• 当链表太长时，递归栈会溢出，程序直接崩掉。

所以它更适合作为“思路展示”给面试官看，不适合作为最终的线上答案。不过理解递归回溯的过程，对理解树、图这类结构性数据的遍历也有帮助，不妨练一练。

2.3 解法三：快慢指针找中点 + 反转后半链表

现在来到正题。这个解法的精妙之处在于：它把链表拆成了两半，后半段原地反转，然后和前半段逐个比较。整个过程只需要有限的几个指针变量，空间复杂度 O(1)。

先分四步走：

第一步，处理特殊情况：空链表和只有一个节点的链表，天然就是回文，直接返回 true。

第二步，用快慢指针找中点。慢指针每次走一步，快指针每次走两步。当快指针到达链表尾部时，慢指针正好停在中间偏右的位置上。这一步需要特别注意循环条件，我在后面第 3.2 节里会专门展开。

第三步，从慢指针所在位置开始，把后半段链表彻底反转。反转之后，原本链表的尾部变成了“新后半段”的头节点。

第四步，用两个指针分别从原链表头和反转后的后半段头开始，同步往后走，逐一比较每个节点的值。只要有一对不同，直接返回 false。如果后半段全部比完还没发现差异，就说明是回文。

这个思路不仅是这道题的答案，也是很多链表题的通用套路：找中点 + 反转 + 合并 / 比较。掌握它，比单纯背会一道道题有用得多。

2.4 三种方式对比，一张表看清差距

注意，第三种方案会破坏原链表结构。后面我们来讨论这个点怎么应对。先记住：如果面试官明确要求“不能修改链表”，那要么在比较完后再把链表恢复回来，要么就退回数组解法。这也是面试中的常见谈判点。

3. 手把手实现：最优解法的完整代码与边界处理

3.1 链表结构定义与答题模板

大多数刷题平台的 C++ 链表结构定义类似这样：

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };

你不需要每次手输构造函数，但一定要清楚next指针可能为nullptr。所有“访问node->next”的操作，前提都是node本身不为空。这道题大量涉及指针移动和反转，提前做好非空判断，能避免一多半的段错误。

3.2 快慢指针找中点：循环终止条件深挖

快慢指针找中点，最核心的就是循环条件的选择。不少初学者会在这直接翻车，所以多写点。

先看最常见的写法：

ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; }

这个循环结束后，slow指向哪里？

• 当链表长度为奇数 5：slow 最终指向第 3 个节点，也就是正中间节点。
• 当链表长度为偶数 4：slow 最终指向第 3 个节点，也就是“后半段”的第一个节点。

这个结果恰好符合我们的需求：从 slow 开始，就是需要反转的后半段。奇数时，中间节点虽然也被划入了“后半段”，但它不需要找谁比对，因为它自己和自己相等；把中间节点一起反转，比较时右半段比左半段多走一个中心节点的位置，但实际上右半段长度只比左半段多 1（比如长度 5，右半段反转后有 3 个节点，左半段有 2 个节点，多出的中心节点会单独和左半段的结尾比较？等下，这听着有点绕。我们实际比较时，用 left 从原头走，right 从反转后半头走，right 的长度是 3，left 的“有效需要比较的长度”也是 3？不对，奇数时 left 和 right 的长度其实都是 3？我们拿 1->2->3->2->1 推一遍：右半段从 slow 指向的 3 开始反转，反转后变成 1->2->3。left 从原头走到 1->2->3->2->1。比较：第 1 次 left=1,right=1；第 2 次 left=2,right=2；第 3 次 left=3,right=3；right 到 nullptr，停止。所以说我们实际比较了 3 次，刚好把整个后半段（含中心节点）和左半段加中心节点比了一遍，因此不能说左半段只需要比较 2 个。这里的关键是：right 的长度为 (n+1)/2，left 从一开始也会走到相应位置，两者步数相同。所以最终用 right 是否为空来控制循环，逻辑成立。对于偶数长度 4，slow 指向第 3 个节点，反转后半 2->1 后 right 长度 2，left 也需要比较前 2 个节点，步数一致。所以结论：while (fast != nullptr && fast->next != nullptr)能够让我们直接从 slow 开始反转，不需要额外的中点前一个节点。

还有另一种循环写法：

while (fast->next != nullptr && fast->next->next != nullptr)

这种写法下，奇数长度时 slow 指向正中间节点；偶数长度时 slow 指向第一个中间节点（偏左）。如果使用这种写法，反转应该从slow->next开始。很多题解就是这么写的。它也有道理，只是后续反转起点不同。

一句话总结：和后面的反转逻辑必须配套，不能混用。我推荐第一种写法，因为它让“反转从 slow 开始”这件事更直白，不容易混乱。但无论哪种，一定要在纸上画出奇数和偶数两种链表，自己推演一遍。

3.3 反转链表迭代实现细节

反转链表是链表操作的基本功，直接给代码：

ListNode* prev = nullptr; while (slow != nullptr) { ListNode* nextNode = slow->next; slow->next = prev; prev = slow; slow = nextNode; }

这里最容易犯的错误是：在slow->next = prev;之后，立刻让slow = slow->next;。这就大错特错了。因为slow->next已经被改成指向 prev，原来的下一个节点早就丢了。正确做法是先用临时变量nextNode保存原来的slow->next，等slow->next修改完毕后，再把slow移动到nextNode。

这个过程不需要额外开辟空间，只用了三个指针变量。反转结束后，prev就是反转后链表的头节点。为了后面比较方便，可以单独用一个变量rightHead保存它，例如：

ListNode* rightHead = prev;

3.4 比较阶段：为什么用 right 指针判空而不是 left

反转完后半段后，链表变成了两条独立的链：

• 左链：原链表前半段，头节点是 head。
• 右链：原链表后半段反转后的结果，头节点是 rightHead。

比较循环常见的正确写法：

ListNode* left = head; ListNode* right = rightHead; while (right != nullptr) { if (left->val != right->val) { return false; } left = left->next; right = right->next; } return true;

有人会想：为什么不用left != nullptr作为循环条件？因为链表长度是奇数时，右链比左链“看起来”短？我们重新思考一下。假设长度为 5，右链长度为 3（含中心节点），左链长度为 5。如果用left != nullptr控制循环，当 right 已经为空时，left 还在原链表的后半段（没有被反转的部分）继续遍历，这时候拿 left 的当前值和 right 的已访问空间（nullptr）做比较就会出问题。但因为我们用 right 判空，循环会在右链遍历结束后自动停住，左链即使还有剩余节点也不用管。换句话说，右链是“有效比较长度”的标尺。

另外要注意：在比较前，原链表后半段已经被反转，所以 left 在走到原链表中心节点之后，会继续沿着“旧的后半段方向”走，从而可能进入一个已经被改写的区域。对于这个问题，同样依赖 right 判空来规避。所以，把右链判空作为循环条件，是这个解法的关键细节。

3.5 完整题解代码（含边界处理）

把以上所有细节拼起来：

bool isPalindrome(ListNode* head) { // 边界：空链表或只有一个节点 if (head == nullptr || head->next == nullptr) { return true; } // 快慢指针找中点 ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } // 反转后半段链表 ListNode* prev = nullptr; while (slow != nullptr) { ListNode* nextNode = slow->next; slow->next = prev; prev = slow; slow = nextNode; } // 逐个比较 ListNode* left = head; ListNode* right = prev; while (right != nullptr) { if (left->val != right->val) { return false; } left = left->next; right = right->next; } return true; }

这段代码可以直接跑过大多数平台的测试用例。时间复杂度 O(n)，空间复杂度 O(1)。唯一的影响是题目要求不允许修改原链表结构的话，需要额外处理。

3.6 要不要恢复链表？这里给你一个明确答案

这可能是这道题最有争议的细节。很多面试官会追问：“你的解法修改了链表，原链表还能用吗？”标准做法是在比较完之后，把后半段链表再反转回去，恢复原结构。

恢复的思路很简单：既然我们在反转后半段之前，并没有专门保存“中点前一个节点”，但我们可以倒推。反转后，原链表的结构是 head -> ... -> 走到原中点前一个节点后再往后就是被反转链的末尾？实际上复杂一些。最简单的方式是：找中点时同时记录中点前一个节点midPrev，反转后半段后不要丢失。如果担心增加实现复杂度，也可以在函数里用两个指针遍历记录。

具体恢复时，把 rightHead 指向的后半段再次反转，然后接到 midPrev 后面。这段代码不复杂，但会让题解长度变长。刷题平台上通常不需要恢复，因为函数返回后链表就会被销毁；但面试时，我建议你主动问一句：“需要我恢复原链表吗？”这既能展示你的思考深度，也能避免和面试官预期不一致。

4. 实操中的高频踩坑与排查实录

4.1 循环条件写错，中点偏移导致结果错误

我在很多地方看到有人这样写：

while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; }

如果后面跟着“从 slow 开始反转”，那就错了。以偶数链表 1->2->2->1 为例，用这个循环，slow 最终指向第二个节点，即第一个 2；而真正应该反转的是从第三个节点开始的“2->1”。如果从第二个节点开始反转，链表就变成了 1->(反转后变成 1->2->2->1? ) 反正比较会错。正确做法是搭配slow->next作为反转起点，或者就把循环条件改成fast != nullptr && fast->next != nullptr。

怎么排查：拿一个长度为 4 和长度为 5 的测试用例，分别打印 slow 的位置，看是否和预期一致。这一步值得做成调试习惯。

4.2 反转时丢掉后继指针

这是链表反转最经典的 bug：

while (slow != nullptr) { slow->next = prev; prev = slow; slow = slow->next; // 错误！此时 slow->next 已经变成 prev }

这句slow = slow->next实际上让 slow 回退到了前一个节点，程序大概率会死循环或者访问空指针。正确必须是：

ListNode* nextNode = slow->next; slow->next = prev; prev = slow; slow = nextNode;

怎么排查：如果程序运行后卡住或者超时，优先检查是不是反转链表时丢了后继。

4.3 比较阶段用错循环条件导致空指针异常

有人会写：

while (left != nullptr) { if (left->val != right->val) return false; left = left->next; right = right->next; }

这个写法在长度是偶数时可能侥幸通过，但长度是奇数时，right 会先变成 nullptr，下一步right->val直接段错误。原因上面已经分析过：right 链的长度是“有效比较长度”，用它判空才成立。

4.4 没有提前处理空链表和单节点

最简单也最容易犯的错。如果没有：

if (head == nullptr || head->next == nullptr) return true;

那么空链表执行head->next会直接崩溃；单节点链表可能因为快慢指针的中点和反转逻辑产生意外结果。这两行看起来不起眼，却必不可少。

4.5 测试用例设计建议

建议准备五组用例：

1. 空链表：NULL
2. 单节点：1
3. 奇数长度回文：1->2->3->2->1
4. 偶数长度回文：1->2->2->1
5. 非回文：1->2->3->1
6. 全相同节点：1->1->1->1->1

特别是第 3 和第 4 组，能覆盖奇偶长度两种路径。跑通这六组，基本可以认为解法在逻辑上没问题。

5. 从这道题延伸出的链表答题方法论

5.1 链表题通用的四步套路

链表题做多了会发现，解法往往有固定套路：

1. 画图：把链表结构画出来，标出每一步指针变化；
2. 边界优先：空链表、单节点、双节点，这些极端情况先确认；
3. 选用合适的技巧：快慢指针、反转、哑节点、合并等等；
4. 用测试用例收尾：奇偶长度、相同节点、重复值都要覆盖。

OR36 这道题几乎完美覆盖了 1、2、3、4，所以把它彻底吃透，能帮你在其他链表题上少走很多弯路。

5.2 双指针题型家族：不止这一道

快慢指针这个概念，在链表题里是一整个家族：

• 环形链表：判断是否有环（快慢指针是否相遇）
• 环形链表起点：找出环的入口节点
• 链表的倒数第 k 个节点：快指针先走 k 步，再同步走
• 链表的中点：就是这个题
• 回文链表：找中点 + 反转

如果你把这几个题放在一起刷，会发现很多代码结构非常相似。刷题最忌讳一题一姿势。通过这道题，把“快慢指针 + 反转”组合技练熟，后面遇到类似问题能形成条件反射。

5.3 面试时怎么表达时空权衡才加分

面试官问你“还有没有更好的解法”时，千万别只说“可以用快慢指针”。更优的表达节奏是：

• 先说暴力数组法：代码简单，空间 O(n)；
• 再优化到快慢指针 + 反转：空间 O(1)；
• 最后主动提一句：“这个做法会修改原链表。如果要求不能修改，我可以在比较完后再反转回来，或者使用递归法。”

这么一说，面试官立刻知道你不光背答案，是真正理解了设计取舍。很多候选人代码写得出来，却说不清楚为什么，这就是失分点。

5.4 手撕这道题时的推荐讲解顺序

建议按照下面这个顺序向面试官展示：

1. 复述题意：判断链表值序列是否回文；
2. 确认约束：能不能修改链表？是否要求空间 O(1)？
3. 讲思路：找中点、反转后半、两指针比较；为什么能这样做；
4. 开始写代码：边写边解释关键步骤；
5. 跑测试：挑一个奇数长度回文和一个偶数长度回文，手动走一遍。

如果你能把“确认约束”这一步做出来，就已经先赢了一半。绝大多数面试官不指望候选人第一版写出完美代码，他们更看重你是否有清晰的边界意识和结构感。

最后再分享一个我自己的习惯

我刷链表题有个固定动作：不管题目多简单，都会在纸上画一条长度为 6 的链表，把所有指针的移动轨迹标出来。特别是这种涉及反转的题，画一遍比看十遍解析都管用。因为链表的指针变化是有“时间顺序”的，一步错、步步错，纸上能非常直观地看出来。

OR36 这道题，我前前后后写过三种解法，每次写都会在“反转后判空条件”上顿一下。但当你把奇偶情况彻底琢磨清楚，脑子里一旦形成“找中点→反转后半→右链判空”这条肌肉记忆，这道题就不再是难题，反而会变成你答链表题时的信心来源。后面再遇到类似的变种，比如判断两条链表是否构成回文、回文链表的所有子序列，你也能很快定位到核心考点。