链表的回文结构这道题，我在不少场合提过：它是链表操作里"基本功的集大成者"。判断一个序列是不是回文，放到数组里是送分题，但一旦装进单向链表，不能随机访问、不能从后往前遍历，难度就上来了。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) 空间解法。思路分三步：

1. 用快慢指针找到链表中点。慢指针每次走一步，快指针每次走两步。快指针走到末尾时，慢指针刚好在中点。
2. 把中点之后的那段链表反转。
3. 用两个指针，一个从头部走，一个从反转后的尾部走，逐个比较节点值。如果全相等就是回文。

为什么快慢指针能找到中点？你想象两个人跑步，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 到 5，slow 到 3，循环条件是fast && fast->next。当 fast 在 5 时，fast->next为空，循环停，slow 停在 3，正好是中点。

当链表有 4 个节点时（偶数），fast 移动一次到 3，slow 到 2；再移动一次 fast 到 NULL，slow 到 3。注意：偶数长度时，slow 停在中点的后一个节点，也就是第 3 个节点，而不是第 2 个。这直接影响后面反转的起点选择。

为什么偶数时 slow 不停在 2？因为快指针走完时是 NULL，慢指针没法"知道"自己应该停在两个中点的前一个。这是快慢指针找中点的固有行为。我们的处理方式很直接：从 slow 开始反转后半段。

比如1 -> 2 -> 3 -> 4 -> NULL，slow 停在 3，反转3 -> 4变成4 -> 3，然后从头指针 head（1）和反转后的头（4）开始比较：1和4不等，返回 false。正确。

再比如1 -> 2 -> 2 -> 1 -> NULL，slow 停在第三个节点 2 的位置，反转后变成1 -> 2（原链表后半段是2 -> 1，反转后头变成了原来的最后一个节点 1）。注意这里我表述容易乱，直接看代码：原链表是1(第一个) -> 2(第二个) -> 2(第三个) -> 1(第四个)，slow 在第三个节点（值为2）。反转从第三个节点开始的链表，也就是反转2(第三个) -> 1(第四个)，得到1(第四个) -> 2(第三个)。然后从 head（值为1）和这个新链表头（值为1）开始比较。依次比较：1==1，接着第二个节点（值为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"); }

在找完中点、反转完链表后分别打印，确认每一步结果符合预期。这里我给出一份自测用例清单，你可以逐个验证：

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。不要觉得这是小题大做，链表题的崩溃九成发生在这一瞬间。把这个习惯刻进肌肉记忆，你会发现所有链表题的正确率都会明显提高。