空间)
1. 从一道面试题说起：为什么链表回文值得单独拎出来讲
链表回文判断这个题目，在算法面试里出现的频率高得离谱。我粗略统计过自己经手过的面试反馈，链表相关的题目里，回文判断能排进前三。原因不复杂：它同时考察了三个核心能力——链表的基本操作、快慢指针的运用、以及空间复杂度的优化意识。一道题能把这三样串起来，性价比极高。
但很多朋友第一次接触这个题的时候，思路是懵的。数组回文好判断，双指针一头一尾往中间夹就行，O(1) 的额外空间，写起来也顺手。链表不行，单向链表你没法从后往前走。于是大部分人第一反应是：把链表的值复制到一个数组里，然后用数组的方式判断。这个思路没错，时间复杂度 O(n)，空间复杂度 O(n)，面试里能拿个及格分，但面试官通常会追问一句“能不能把空间降到 O(1)”。这一问，才是这道题真正的分水岭。
这篇文章就是冲着这个追问来的。我会把从 O(n) 空间到 O(1) 空间的完整优化路径拆开讲清楚，包括快慢指针怎么找中点、链表怎么原地反转、反转之后怎么比较、比较完怎么把链表恢复原状。每一步都会给出完整的 C++ 代码，并且解释为什么这么写、哪里容易写错。适合已经会写基础链表操作、想在面试里把这道题答漂亮的朋友，也适合刚学数据结构、想通过一个具体例子把指针操作彻底搞明白的同学。
提示：本文所有代码基于 C++11 及以上标准，使用
nullptr而非NULL，结构体定义采用 LeetCode 风格的ListNode。
2. 核心思路拆解：三种解法与它们的取舍逻辑
2.1 最直观的解法：辅助数组法
先把链表遍历一遍，把每个节点的值存进vector或者数组，然后用双指针从两端向中间比较。这个思路的代码大概长这样：
bool isPalindrome(ListNode* head) { vector<int> vals; ListNode* cur = head; while (cur != nullptr) { vals.push_back(cur->val); cur = cur->next; } int left = 0, right = vals.size() - 1; while (left < right) { if (vals[left] != vals[right]) return false; left++; right--; } return true; }时间复杂度 O(n)，空间复杂度 O(n)。这个解法在面试里不是不能用，但它有个隐含问题：如果链表特别长，比如几百万个节点，额外开一个等长的数组可能导致内存吃紧。面试官问“能不能优化空间”，就是在暗示你往 O(1) 方向想。
2.2 进阶解法：快慢指针找中点加原地反转
这是本文的重点。核心思路分四步：
- 用快慢指针找到链表的中点。
- 把中点之后的半条链表原地反转。
- 从头部和反转后的半条链表头部同时出发，逐个比较值。
- 比较完成后，把反转的半条链表再反转回来，恢复原链表结构。
这四步里，第一步和第二步是难点，第四步是很多人会忽略的“加分项”。为什么第四步重要？因为在实际工程里，函数不应该有副作用。你判断完回文，链表结构被改了，调用方如果还指望用这个链表做别的事，就出问题了。面试里主动做恢复，是一个很能体现工程素养的细节。
空间复杂度 O(1)，因为我们只用了几个指针变量。时间复杂度 O(n)，找中点遍历 n/2，反转遍历 n/2，比较遍历 n/2，恢复再遍历 n/2，加起来还是 O(n)。
2.3 递归解法：优雅但空间不达标
还有一种递归写法，利用递归栈从后往前比较。思路是递归到链表末尾，然后借助函数返回的过程反向遍历。代码写起来很简洁，但递归深度等于链表长度，空间复杂度是 O(n) 的栈空间。面试里如果面试官明确要求 O(1) 空间，递归法就不合格。这里提一句是为了让你知道有这条路，但本文不展开，重点放在 O(1) 的迭代法上。
2.4 三种解法的对比
| 解法 | 时间复杂度 | 空间复杂度 | 是否修改链表 | 面试推荐度 |
|---|---|---|---|---|
| 辅助数组法 | O(n) | O(n) | 否 | 及格，可作起步回答 |
| 快慢指针+反转 | O(n) | O(1) | 是（可恢复） | 最优，强烈推荐 |
| 递归法 | O(n) | O(n) | 否 | 一般，空间不达标 |
从表格能看出来，快慢指针加反转的方案在空间上碾压另外两种。接下来我把这个方法拆成几个关键环节，逐个讲透。
3. 关键环节逐一拆解：指针怎么走、边界怎么处理
3.1 快慢指针找中点：奇数长度和偶数长度的区别
快慢指针的基本设定是：慢指针slow每次走一步，快指针fast每次走两步。当fast走到链表末尾时，slow刚好在中间位置。
但这里有个细节必须搞清楚：链表长度是奇数还是偶数，slow停的位置不一样。
- 奇数长度，比如
1->2->3->2->1，slow最终停在正中间的3。 - 偶数长度，比如
1->2->2->1，slow最终停在后半段的第一个2。
这个区别直接影响后面反转的起点。对于奇数长度，中间那个节点自己跟自己对称，不需要参与比较，所以反转应该从slow->next开始。对于偶数长度，slow停的位置就是后半段的起点，反转从slow开始。
那怎么统一处理？有两种常见写法。
写法一：让fast从head开始，循环条件用fast != nullptr && fast->next != nullptr。这样循环结束时，slow停在的位置对于奇数是正中间，对于偶数是后半段第一个。然后反转时统一从slow->next开始，但偶数情况下这样会漏掉slow自己。所以这种写法需要额外处理。
写法二：让fast从head->next开始，循环条件用fast != nullptr && fast->next != nullptr。这样循环结束时，slow停在的位置对于奇数是正中间的前一个，对于偶数是前半段的最后一个。然后反转统一从slow->next开始，两种情况都正确。
我推荐写法二，因为它把奇偶两种情况统一了，代码更干净。具体代码：
ListNode* slow = head; ListNode* fast = head->next; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } // 此时 slow->next 就是需要反转的半条链表的起点拿1->2->3->2->1走一遍：初始slow=1, fast=2。第一轮slow=2, fast=2（因为 fast 从 2 走两步到 2）。等等，这里要仔细。fast初始是head->next即节点2。循环条件fast != nullptr && fast->next != nullptr成立。执行slow = slow->next变成节点2，fast = fast->next->next变成节点2（从节点 2 走两步：先到 3，再到 2）。下一轮条件：fast是节点2，fast->next是节点1，成立。执行slow变成节点3，fast变成nullptr（从节点 2 走两步：先到 1，再到空）。循环结束。此时slow是节点3，slow->next是节点2。反转从节点2开始，得到1->2，正好是后半段。正确。
再拿1->2->2->1走一遍：初始slow=1, fast=2。第一轮slow=2（第一个2），fast从节点 2 走两步到节点 1。第二轮条件：fast是节点 1，fast->next是节点 1 的下一个即节点 1（第二个1），成立。执行slow变成第二个 2，fast变成nullptr。循环结束。slow是第二个 2，slow->next是节点 1。反转从节点 1 开始，得到1->2，正好是后半段。正确。
注意：快指针的初始位置是
head->next而不是head，这是统一奇偶处理的关键。很多人在这一步写错，导致偶数长度时中点偏后，反转后比较出错。
3.2 原地反转链表：三指针法的标准写法
反转半条链表，用的是经典的三指针法。假设反转起点是cur，我们需要三个指针：prev、cur、next。
ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }这段代码的逻辑是：每次把cur的next指向prev，然后三个指针整体往后挪一格。循环结束时cur是nullptr，prev指向原来的尾节点，也就是反转后的头节点。
这里有个容易踩的坑：next指针必须在修改cur->next之前保存。如果你先写cur->next = prev，那cur原来的下一个节点就找不到了，链表直接断掉。这个顺序问题在面试手写代码时特别容易出错，因为紧张的时候手比脑子快。
3.3 比较两个半段：什么时候停、怎么判断
反转完成后，我们有两个头指针：一个是原链表的head，另一个是反转后的半条链表的头，记为secondHalf。
比较的逻辑是：同时从head和secondHalf出发，每次比较两个节点的值，不相等就返回false，相等就各自往后走一步。什么时候停？当secondHalf走到nullptr时停。
为什么是secondHalf先到空？因为后半段的长度一定小于等于前半段。对于奇数长度，后半段比前半段少一个节点（中间那个节点不算）。对于偶数长度，两段等长。所以以secondHalf为准是安全的。
ListNode* p1 = head; ListNode* p2 = secondHalf; while (p2 != nullptr) { if (p1->val != p2->val) return false; p1 = p1->next; p2 = p2->next; } return true;这里不需要判断p1是否为空，因为p2走到空的时候p1一定还没走到空（或者刚好走到空，对于偶数长度）。
3.4 恢复链表：为什么这一步不能省
比较完成后，反转的那半条链表还是反着的。如果不恢复，原链表的结构就被破坏了。虽然在很多在线判题系统里，函数返回后链表不再被使用，不恢复也能过，但在实际工程代码里，修改入参是一个危险行为。
恢复的方法很简单：把secondHalf再反转一次，然后接到slow->next上。
slow->next = reverseList(secondHalf);因为reverseList返回的是反转后的新头，而原来的slow->next在反转后变成了尾节点，所以直接把反转结果赋给slow->next就完成了恢复。
提示：恢复操作在面试里是加分项。你可以在写完主体逻辑后主动说一句“我把链表恢复一下，避免修改入参”，面试官会对你刮目相看。
4. 完整代码实现与逐行注释
把上面所有环节拼起来，得到完整的 C++ 代码：
#include <iostream> struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // 反转以 head 为起点的链表，返回反转后的头节点 ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; // 先保存下一个节点 cur->next = prev; // 当前节点指向前一个 prev = cur; // prev 后移 cur = next; // cur 后移 } return prev; // prev 最终指向原链表的尾节点，即反转后的头 } bool isPalindrome(ListNode* head) { // 空链表或单节点链表，直接是回文 if (head == nullptr || head->next == nullptr) { return true; } // 第一步：快慢指针找中点 ListNode* slow = head; ListNode* fast = head->next; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } // 此时 slow->next 是后半段的起点 // 第二步：反转后半段 ListNode* secondHalf = reverseList(slow->next); // 第三步：比较前半段和反转后的后半段 ListNode* p1 = head; ListNode* p2 = secondHalf; bool result = true; while (p2 != nullptr) { if (p1->val != p2->val) { result = false; break; } p1 = p1->next; p2 = p2->next; } // 第四步：恢复链表结构 slow->next = reverseList(secondHalf); return result; }这段代码可以直接复制到 LeetCode 的 234 题提交。我实测过，运行时间和内存占用都排在前面。
4.1 手动模拟一遍执行过程
拿1->2->3->2->1走一遍完整流程：
初始：head = 1，链表为1->2->3->2->1。
找中点：slow最终停在3，fast变成nullptr。slow->next是2。
反转后半段：从2开始反转2->1，得到1->2。secondHalf指向1。
比较：p1从1开始，p2从1开始。第一轮1==1，p1到2，p2到2。第二轮2==2，p1到3，p2到nullptr。循环结束，返回true。
恢复：把secondHalf即1->2再反转，得到2->1，接到slow->next上。链表恢复为1->2->3->2->1。
再拿1->2->2->1走一遍：
找中点：slow停在第二个2，fast变成nullptr。slow->next是1。
反转后半段：从1开始反转，得到1。secondHalf指向1。
比较：p1从1开始，p2从1开始。第一轮1==1，p1到2，p2到nullptr。循环结束，返回true。
恢复：把1反转还是1，接到slow->next上。链表恢复。
4.2 边界情况测试清单
写完代码后，我习惯用下面这组用例跑一遍：
| 用例 | 预期结果 | 考察点 |
|---|---|---|
nullptr | true | 空链表 |
1 | true | 单节点 |
1->2 | false | 两节点不等 |
1->1 | true | 两节点相等 |
1->2->1 | true | 奇数长度回文 |
1->2->3 | false | 奇数长度非回文 |
1->2->2->1 | true | 偶数长度回文 |
1->2->3->1 | false | 偶数长度非回文 |
这八个用例覆盖了所有边界，每次写完链表题我都跑一遍，能挡掉大部分低级错误。
5. 常见问题与排查技巧实录
5.1 快慢指针循环条件写错导致死循环
最常见的错误是把循环条件写成fast != nullptr && fast->next != nullptr但fast初始是head。这样在偶数长度时，slow会停在中间偏后的位置，导致反转起点错误。更严重的是，如果fast初始是head且链表长度为 1，循环条件fast->next != nullptr直接不成立，slow停在head，slow->next是nullptr，反转空链表返回nullptr，比较时p2是nullptr，循环不执行，返回true。这个结果碰巧是对的，但逻辑是错的，换成长度 2 的链表就暴露了。
排查方法：拿1->2和1->2->3两个用例手动走一遍，看slow停在哪。
5.2 反转链表时指针顺序写反
前面提过，next必须在修改cur->next之前保存。我见过有人写成：
cur->next = prev; prev = cur; cur = cur->next; // 错误！此时 cur->next 已经指向 prev 了这样cur会往回走，形成死循环。正确的顺序是保存next、修改cur->next、移动prev、移动cur。
5.3 比较循环的终止条件搞混
有人用while (p1 != nullptr && p2 != nullptr)作为比较循环的条件。这样在奇数长度时，p2先到nullptr，循环结束，返回true，结果是对的。但在某些边界下，比如1->2->3，p1和p2会同时到nullptr吗？不会，p2先到。所以这个条件也能工作，但不如while (p2 != nullptr)清晰。我建议统一用p2作为终止条件，因为后半段一定先走完。
5.4 忘记恢复链表导致后续操作出错
这个在面试里不一定会被扣分，但在实际项目里是隐患。我个人的习惯是，只要函数修改了入参，就一定恢复。恢复的代码只有一行，成本极低，但体现了对调用方的尊重。
5.5 常见问题速查表
| 问题现象 | 可能原因 | 解决方法 |
|---|---|---|
| 偶数长度链表返回错误结果 | 快指针初始位置错误 | 改为fast = head->next |
| 程序死循环 | 反转时指针顺序错误 | 先保存next再修改cur->next |
| 奇数长度链表比较越界 | 比较循环条件用了p1 | 改用p2 != nullptr |
| 链表结构被破坏 | 忘记恢复 | 比较后再次反转并接回 |
| 空链表崩溃 | 没有处理head == nullptr | 开头加空判断 |
提示：链表题最好的调试方式不是打断点，而是画图。拿张纸把每个指针的位置画出来，一步一步走，比盯着代码看快得多。
6. 从这道题延伸出去：还能怎么玩
6.1 判断回文子链表
如果题目改成“判断链表中从第 i 个节点到第 j 个节点是否构成回文”，快慢指针的思路依然适用，只是需要先定位到第 i 个节点，然后对子链表做同样的操作。定位可以用一次遍历完成，整体复杂度不变。
6.2 找到最长的回文子链表
这个问题难度直接上了一个台阶。暴力解法是枚举所有子链表判断回文，O(n^3)。优化思路可以借鉴字符串里 Manacher 算法的思想，但链表没法随机访问，实现起来更复杂。面试里如果遇到，可以先给出暴力解，再讨论优化方向。
6.3 双向链表的回文判断
双向链表就简单多了，一头一尾两个指针往中间夹就行，O(n) 时间 O(1) 空间，不需要反转。这也从侧面说明，单向链表的很多操作之所以复杂，就是因为缺少从后往前的遍历能力。
6.4 实际工程中的应用场景
链表回文判断在工程里直接用的场景不多，但它背后的两个技术点——快慢指针找中点和原地反转——用得非常多。比如：
- 找链表的中间节点，用于归并排序链表。
- 反转链表的前 k 个节点，用于分组反转。
- 判断链表是否有环，快慢指针的经典应用。
把这道题吃透，相当于把链表操作的核心套路都练了一遍。
我个人在实际刷题和面试中的体会是，链表题不怕难，就怕指针指来指去把自己绕晕。我的习惯是每写一行涉及指针修改的代码，就在纸上同步画一下当前状态。这个方法看起来很笨，但能挡掉九成以上的指针错误。另外，写完代码后一定要拿边界用例跑一遍，空链表、单节点、两节点、奇数长度、偶数长度，这五个用例跑完，基本就稳了。最后再分享一个小技巧：如果你在面试里一时想不出 O(1) 空间的解法，先把 O(n) 的辅助数组法写出来，保证有一个能跑的版本，然后再跟面试官讨论优化方向。这样比卡在那里什么都不写要好得多。
