空间最优解)
提到单链表的回文结构，我见过太多人第一反应就是：遍历一遍，把值全存进数组，再两头一比对完事。这个思路确实能过在线评测，可你一旦去面试，对面大概率会追问一句：“能不能做到 O(1) 空间？”到这一步，很多人就开始支支吾吾了。说到底，单链表的回文判断不只是“判断”这么简单，它考察的是你对单向遍历限制的理解、对链表反转的熟练度、以及处理边界条件的基本功。这篇文章我就把从暴力解法到最优解法的路线完整走一遍，顺便把空链表、不带头结点、循环单链表这些容易翻车的场景都聊透。
1. 单链表回文判定的难点到底卡在哪里
1.1 先明确回文结构在链表语境下指什么
回文结构就是正着读和倒着读完全一样。放到链表中，比如1 -> 2 -> 3 -> 2 -> 1，这个序列正着读和倒着读都是 1、2、3、2、1，所以它是回文链表。这里有一个很多人忽略的前提：我们判断的是“节点值构成的序列”是否对称，不是“节点指针”是否对称。哪怕是两个不同的节点对象，只要它们的 val 相等，在回文判定里就算匹配。
做这道题之前，还需要保证单链表的基本操作是闭着眼都能写的水平。最近热搜里有很多“在指定位置插入建立单链表”、“单链表的清空”这类词，其实它们都是回文判断的前置技能。比如在指定位置插入节点，核心就是三步：先遍历到目标位置的前驱节点，再把新节点的 next 指向前驱的 next，最后把前驱的 next 指向新节点。清空链表则要先把当前节点的 next 保存下来再置空，否则你还没来得及取下一个节点，指针就丢了。这些基本功不稳，后面写回文判断的代码很容易七零八落。
1.2 单向遍历是核心矛盾
数组判断回文太简单了：左右两个下标，一个从头往后，一个从尾往前，中间碰头就结束。为什么？因为数组支持随机访问，你能同时拿到头和尾。
单链表只有 next 指针，你只能从头走到尾，但没法从尾走到头。除非你先遍历一遍记住路径，或者把链表结构临时改掉。所以，回文判断的所有解法，本质上都是在回答一个问题：如何获得“从尾到头”的访问能力。
- 用辅助数组，就是把尾部访问能力提前存好；
- 用递归，是让函数调用栈天然保留从尾到头的回溯路径；
- 用反转，是让后半段链表临时翻过来，把尾到头变成头到尾。
想明白这一点，你再看那些五花八门的题解，就会觉得它们其实是同一道题的不同回答方式。
1.3 值比较和结构比较不是一回事
很多人把回文链表和链表反转搞混，这正好解释了为什么热搜里会出现“python单链表逆序”。反转链表是把所有 next 指针掉头，而回文判断里我们也会用到反转，但只是把反转当作一个工具来获得反向遍历能力。这里有个关键约束：反转操作必须可逆。如果比较完之后链表已经面目全非，在工程里就是事故。所以最优解法里，判断完再把后半段翻回去，不只是一个加分项，而是负责任的做法。
2. 辅助数组法：保底可用，但别拿它当终点
2.1 代码与思路
思路直白到不需要解释：
- 遍历链表，把每个节点的 val 依次放进数组；
- 得到数组后，用双指针从两端向中间比较，或者直接逆序比较。
Python 实现：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def is_palindrome(head): vals = [] cur = head while cur: vals.append(cur.val) cur = cur.next left, right = 0, len(vals) - 1 while left < right: if vals[left] != vals[right]: return False left += 1 right -= 1 return TrueC++ 写起来也差不多，vector 一存就结束了。一个小细节：不要图省事直接写return vals == vector<int>(vals.rbegin(), vals.rend())，虽然能过，但会多一次拷贝和一次完整比较，数据量大的时候没必要。双指针法更干净。
2.2 复杂度看得明明白白
时间复杂度 O(n)：遍历链表 O(n)，数组比较 O(n)。空间复杂度 O(n)：数组要存 n 个元素。如果节点值是整数，这个开销不算大；但如果是字符串或者结构体，占用就会非常明显。
有人会问：那我把链表的值取出来放数组，和字符串回文判断有什么两样？确实，这个方案本质上是把链表降维成了数组，等于放弃了链表结构本身的特点。这也是为什么我说“保底可用，但别拿它当终点”。
2.3 这个方案的适用场景
不是说数组法没用。实际工作中，如果链表长度不大，比如几千个节点以内，而且节点值是轻量数据，用数组法是最不容易出错的方案。笔试题、快速验证思路、给同事解释需求，都可以先写它。我自己刷题有个习惯：遇到不太确定的链表题，先写一个能跑通的暴力版本做兜底，确认边界行为之后，再考虑怎么优化成 O(1) 空间。这样心里有底，不会在考场上面面相觑。
2.4 如果允许额外空间，其实还有更快做法
如果额外空间允许，还有一个介于“全存数组”和“原地反转”之间的方案：用快慢指针找到中点，把后半段压入栈，再从头遍历并弹栈比较。空间复杂度还是 O(n)，但只需要存后半段，省了大约一半空间。
def is_palindrome_stack(head): if not head or not head.next: return True slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next stack = [] cur = slow while cur: stack.append(cur.val) cur = cur.next cur = head while stack: if cur.val != stack.pop(): return False cur = cur.next return True这个方案的好处是逻辑直观：栈的后进先出天然模拟了反向遍历。面试时如果被要求“你写一个能跑通的解法”，优先写数组法或栈法都行；但如果被追问空间复杂度，就必须往下看第四节的方案了。
3. 递归回溯法：用系统栈换反向遍历
3.1 核心逻辑
递归回溯法的原理是：当函数递归到链表最后一个节点时，递归调用的返回过程恰好是按“从尾到头”的顺序进行的。于是我们可以让一个从头部开始的指针，在回溯过程中和递归位置逐对比较。
你可以这样类比：一群人排成一列，你从头开始走，另一只“递归指针”从尾部倒着走回来。每走一步，两边各报一个数，如果所有数都对应相等，就是回文。
3.2 完整代码
def is_palindrome_recursive(head): left = head def dfs(right): nonlocal left if right is None: return True if not dfs(right.next): return False if left.val != right.val: return False left = left.next return True return dfs(head)这段代码的精髓在于：dfs(right.next)会一直钻进尾节点，返回途中 right 依次是尾节点、倒数第二个节点……而 left 是头节点、第二个节点……两者逐一对比。
这里有一个非常关键的细节：left变量必须声明为nonlocal。因为我们要在递归内部修改外部变量，如果不声明，Python 会把它当作一个新的局部变量来处理，代码直接报错。如果你用的是支持闭包但语法不同的语言，也一定要注意这个“修改外部捕获变量”的机制。
3.3 递归的代价与坑
先说代价。递归深度等于链表长度。链表长度几千个节点时没问题，但如果链表有几万、几十万个节点，Python 默认递归深度限制在 1000 左右，你会在几毫秒内看到一个 RecursionError；在 C++ 里则是栈溢出或者段错误。工程上处理链表经常是百万级数据，递归方案基本没法用。
另一个小坑是 left 指针的更新时机。如果你在递归向下深入的过程中移动 left，那就全错了，必须在回溯阶段移动。换句话说，先等递归到底，再开始比较。递归回溯法在空间复杂度上依然是 O(n)，因为函数调用栈本身占用了 O(n) 空间。
那它值得学吗？值得。虽然它不是最优解，但它能帮你理解递归和系统栈的关系。很多树形结构问题，比如判断二叉树是否对称、二叉树的镜像等，都用到了这种“先递归到叶子，再回溯处理”的模式。把链表的递归回溯吃透，后面学树的遍历会轻松很多。
4. 快慢指针+后半段反转：O(1)空间的毕业级方案
4.1 整套流程概述
这是面试官最想看到的方案，时间和空间双优：
- 用快慢指针找到链表的中点；
- 反转后半段链表；
- 从头部和反转后的后半段头部分别出发，逐个比较；
- 把后半段再反转回去，恢复原链表。
为什么快慢指针能找到中点？因为快指针走两步、慢指针走一步，当快指针到达末尾时，慢指针正好走了一半。这个“快慢同步”的技巧也常用于链表环检测、找链表中点等问题，回文判定只是它的一次应用。
4.2 代码实现与每步解释
def reverse(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev def is_palindrome(head): if head is None or head.next is None: return True # 1. 快慢指针找中点 slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 2. 反转以 slow 为起点的后半段链表 second_head = reverse(slow) # 3. 比较前半段和反转后的后半段 first = head second = second_head while second: if first.val != second.val: reverse(second_head) # 恢复链表 return False first = first.next second = second.next # 4. 恢复链表 reverse(second_head) return True我逐段拆开讲：
- 找中点：循环条件是
while fast and fast.next。迭代结束后，对于奇数长度的链表，slow指向最中间的节点；对于偶数长度的链表，slow指向后半段的第一个节点。两种情况下，把slow作为后半段起点反转都是安全的。 - 反转函数：
prev初始为 None，cur从 slow 开始，不断把当前节点的 next 指向前一个节点。这个操作会修改链表结构，所以必须清楚自己在做什么。 - 比较：以反转后的后半段
second作为循环条件，一旦second遍历完，就说明全部比较完毕。奇数长度时，前半段多出的那个中间节点会在循环里和反转后的后半段头节点自比一次，不影响结果。 - 恢复：
reverse(second_head)把后半段再次反转，接回原来的形状。
4.3 两个容易让人绕晕的细节
第一个细节：为什么比较阶段循环条件是while second而不是while first？
因为后半段的长度小于等于前半段，用后半段做终止条件能自然退出。如果你用 first 做条件，偶数长度没问题，奇数长度时 first 会先遍历完，此时 second 还没被完全消费。虽然结果上可能不影响判断，但代码的可读性变差了，也容易在边界条件下出错。
第二个细节：恢复链表时，为什么只用对second_head再反转一次就够了？
因为整个操作只改变了后半段内部的 next 指向，前半段的指针全都原封不动。前半段的尾节点仍然指向 slow 节点。你把反转后的后半段再反转一次，后半段又恢复成原来的顺序，前半段和后半段的连接关系也就自然恢复。不需要额外维护什么断点指针。
4.4 测试用例验证
写代码容易，跑对测试才是真功夫。我之前也是反复试错才确认下面这些用例全部通过：
| 输入链表 | 预期结果 | 说明 |
|---|---|---|
[] | True | 空链表按普遍定义视为回文 |
[1] | True | 单节点天然回文 |
[1, 1] | True | 偶数长度最小回文 |
[1, 2] | False | 偶数长度非回文 |
[1, 2, 1] | True | 奇数长度回文 |
[1, 2, 2, 1] | True | 偶数长度回文 |
[1, 2, 3, 2, 1] | True | 标准奇数回文 |
[1, 2, 3, 2, 3] | False | 尾部不一致 |
奇数长度和偶数长度下 slow 的落点不同，但算法都能正确处理，正好说明上面两个细节没有踩坑。
5. 边界条件与常见翻车点
5.1 空链表、单节点到底返回什么
先说结论：我这里把空链表和单节点链表都视为回文。空链表没有值序列，说它是回文在逻辑上叫“空真”；单节点天然对称，因为正着读和倒着读都是同一个数。很多教科书题目也默认这个规则，LeetCode 上也是这么判的。
不过，万一遇到一个自定义题目，它可能规定“空链表不是回文”，那也合理。我的建议是：在函数文档注释里写清楚自己的判定标准，避免阅读代码的人产生歧义。比如：
def is_palindrome(head): """空链表和单节点链表均视为回文。""" ...5.2 偶数长度下快慢指针的终止条件
这是一个非常经典的写错位置。如果你写的是while fast.next而不是while fast and fast.next，遇到偶数长度链表时，fast 会先变成 None，再访问fast.next就会抛空指针异常。
实测中，很多初学者都在这里翻车。还有一种写法是把slow初始化为head.next，这看起来可以少走一步，但在回文判断里会让中点产生偏移，导致反转后半段出错。建议按统一模板：fast 和 slow 都从 head 出发，循环条件写while fast and fast.next。这样无论链表长度是奇是偶，slow 的落点都正好符合我们的预期。
5.3 不带头结点的单链表怎么处理
不带头结点意味着 head 本身就是第一个数据节点，上面所有的代码都直接适用。但如果你拿到的是带头结点（哑节点）的链表，那就必须先跳过哑节点，否则会把哑节点当成一个值参与比较，导致结果全错。
带头结点的处理方式很简单：
def is_palindrome_with_dummy(dummy_head): return is_palindrome(dummy_head.next)同理，清空单链表的时候如果中间有循环引用，也需要格外小心。所谓清空，就是把所有节点的引用关系断开，让 GC 或手动释放能够回收内存。在 Python 里，你只需要把 head 置为 None，后面无人引用的节点就会被回收；但在 C/C++ 里，你必须逐个节点 delete，否则就是内存泄漏。
5.4 恢复链表为什么是加分项
很多算法答案只求出结果，不考虑破坏原链表。但在工程中，传入一个链表，函数不应该默默把链表结构改写掉。面试时，如果你能在比较完之后把链表恢复原状，这个细节会非常加分。做法上面已经给了：比较结束后再reverse(second_head)一次。
但有一个容易忽略的点：当比较到中途发现不相等，直接 return False 的时候，也要先恢复链表再返回。否则链表就是残缺的。在递归版里也是同理，不建议因为“反正结果都出来了”就不管链表变成什么样。这是一个职业习惯问题。
6. 延伸思考：循环链表、双向链表与真实世界的回文判断
6.1 循环单链表的回文判断思路
热搜词里出现了“循环单链表”，这里专门说一句。如果链表尾节点的 next 指向头节点，就形成了环，那常规快慢指针找中点的思路没法直接用了，因为你不知道哪里是“末尾”。
我的实践思路是：先用快慢指针判断链表是否成环，并找到环的入口位置。然后从某个确定的起点出发，遍历一轮来统计链表长度，把循环问题等价成一条线性链表，再套用本文的三种方法之一。换句话说，回文判断建立在“知道链表边界”之上，循环链表本身不是回文判断的典型场景，但只要理解了环的构成，思路是相通的。
6.2 双向链表反而简单
如果链表有 prev 指针，回文判断会变得非常舒服：tail 从末尾往前走，head 从前往后走，双指针直接向中间汇合。这就是“双向访问能力”带来的优势。你在做单链表题目时感受到的所有别扭，在双向链表里都会消失。这正是为什么学习单链表时，老师总强调“单向遍历的约束”——它就是无数链表题目的题眼。
6.3 回文检测在工程里的身影
可能有人觉得链表回文判断只是面试题。其实回文检测在生物信息和文本处理里非常常见，比如基因序列中的回文片段、DNA 限制性内切酶识别位点、校验码设计，以及一些日志链路中需要检测镜像形态的节点。现实中大量回文检测发生在字符串上，但字符串底层往往也是顺序表或链表结构。理解这个算法的本质，对处理“顺序访问受限的数据结构”是有迁移价值的。
我自己刷题时踩过一个大坑：用递归法测试一个几万节点的链表，直接就把递归栈打爆了，环境都崩溃了。后来才意识到，动手前先分析数据规模和运行环境，比急着把代码写出来更重要。如果你现在也在练链表相关题目，我的建议是：先把基本操作练到闭眼能写，再考虑进阶方案；遇到回文判断，优先能写出数组法保底，再挑战快慢指针法，最后把恢复链表的细节刻在脑子里。这样不管面试官怎么追问，你都不至于懵。
