1. 题目与核心思路拆解

1.1 回文链表到底在考什么

回文链表这道题，在主流刷题平台的 Hot 100 榜单里长期占据前排位置。我第一次刷的时候，觉得很简单，链表的节点值放进数组，左右双指针一比对，不就完事了吗？后来真到面试模拟环节，面试官追问“能不能做到空间复杂度 O(1)”，我才意识到这道题的精髓根本不在“判断是否回文”，而是藏在“原地判断”这几个字里。

它要求判断一个单链表是否为回文链表，也就是正着读和倒着读的顺序完全一致。比如1 -> 2 -> 2 -> 1是回文，1 -> 2不是。这类问题在本质上考的是三个基本功的组合：找链表中点、反转链表、双指针遍历。这三个点单独拿出来都不算难，但组合在同一题里，很多人就会在各种边界条件下翻车，所以它很适合作为面试开场题，能快速看出一个人对链表操作是否真的熟练。

1.2 为什么这道题值得反复做

刷题不能只追求 AC（Accepted），我习惯把一道题拆成多个层次去理解。回文链表这道题正好处在“简单题不会太简单，难题又不至于太复杂”的黄金位置上。如果你只会用数组，那道题对你来说就是一个普普通通的简单题；但如果你能讲出 O(1) 空间解法，并解释清楚反转后半段链表的过程中指针是如何变动的，那这道题就能体现出你和普通刷题人之间的差距。

从实际面试角度看，链表相关题目出现频率很高，而回文链表又是一个非常经典的组合考点。相比直接问“反转链表”这种单一考点，回文链表更接近真实业务中“既要读取数据，又要避免破坏原始结构”的思维方式。很多工程问题里，你需要在尽量少用额外空间的前提下，对一份链式存储的数据做校验，回文链表就是一个非常好的训练场景。

1.3 题目约束与前置知识

题目通常会给出单链表的头节点head，要求返回一个布尔值。链表长度可能是空链表，也可能只有一个节点。这两类边界情况很多人会漏掉，空链表和单节点链表按定义都是回文，必须直接处理。我们需要掌握的链表基本操作包括：

• 遍历链表并统计节点值；
• 使用快慢指针寻找中间节点；
• 反转一段链表；
• 连接和恢复链表结构。

如果你对反转链表还不熟练，建议先单独刷 1 到 2 道反转链表变体题，再来碰回文链表。否则你在写最优解时，很容易在指针赋值那一行卡住。

2. 解法一：数组双指针判断回文链表

2.1 先说最容易想到的思路

遇到回文判断，最直觉的做法就是把链表还原成数组。因为链表只能从头到尾单向遍历，无法直接从尾部往前访问，而数组支持随机访问，拿到所有元素之后，问题就变成了“判断一个数组是否回文”。这个思路在竞赛和面试中都可以作为第一反应说出来，至少证明你理解了回文的基本定义。

具体步骤很简单：

1. 从head开始遍历整个链表，把每个节点的val依次放入一个列表；
2. 设置左指针left = 0，右指针right = len(vals) - 1；
3. 当left < right时，比较vals[left]和vals[right]，不相等就直接返回False；
4. 相等则left += 1，right -= 1，循环结束后返回True。

这个过程非常像处理字符串回文。你不需要考虑链表结构，只需要关心节点值的顺序。实现代码也极短：

def isPalindrome(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 True

2.2 数组解法的复杂度与局限

数组解法的时间复杂度是 O(n)，空间复杂度也是 O(n)，因为需要额外保存整个链表的节点值。如果题目没有额外限制，这种解法完全正确，而且不容易出错，适合作为第一版代码。

但面试中一旦追问空间复杂度，你就需要马上能进入下一层。这是很多人容易慌的地方。你需要主动说：“这个解法空间复杂度 O(n)，如果要求 O(1) 空间，我可以改用快慢指针配合局部反转。”这句话本身就是加分项。

在实际生产环境中，如果链表非常长，比如几十万个节点，把所有值都拷贝到数组里会导致内存消耗上升。更合理的做法是只在链表上做有限几个指针的移动。这也是为什么数组解法通常只作为热身思路，而不是最终答案的原因。

2.3 为什么我建议你还是要先写一遍数组解法

不要因为空间复杂度不够优秀就完全跳过这个解法。我自己的刷题习惯是：先写能跑通的暴力解，再去优化。因为暴力解能帮你确认题目理解没有偏差，也给你后续做测试样例对比提供基础。

另外，数组解法在处理负数节点值时依然有效，不需要特殊判断。你可以用它作为正确性基准，去验证后面的 O(1) 空间解法是否在某些边界条件下出错。写最优解前先在本地跑几个用例，用数组解法的结果去对拍，这样可以省下很多调试时间。

3. 解法二：快慢指针加反转后半链表，最优解的核心理解

3.1 三步走：找中点、反转后半段、双端比较

要写出 O(1) 空间解法，最经典的思路是把链表后半段反转，然后从两头同时向中间比较。整个流程可以拆成三块来看。

第一步，找到链表的中间节点。这里我默认使用快慢指针：慢指针slow每次走一步，快指针fast每次走两步。当fast到达链表末尾时，slow恰好停在中间位置。对于偶数长度的链表，slow会停在中间偏右的节点上；对于奇数长度，slow正好停在正中间节点上。

第二步，从slow开始，把后半段链表原地反转。这一步可以复用标准的反转链表模板：定义prev = None，cur = slow，然后循环里用一个变量保存cur.next，再让cur.next指向prev，最后三个指针集体移动。反转完成后，后半段的头节点变成了原来的尾节点。

第三步，用两个指针同时遍历比较。左指针指向原链表头head，右指针指向反转后的后半段头。只要右指针没到达末尾，就比较左右两个节点的值。如果出现不相等，则不是回文。这里要注意奇偶长度下循环条件的区别，我马上在下面单独细说。

3.2 奇偶长度下到底怎么确定循环条件

这是最容易写错的地方，也是面试官最爱追问的细节。先说结论：我们可以统一用while right:来作为比较循环的判断条件，其中right是反转后的后半段头指针。

举个例子，奇数长度链表1 -> 2 -> 3 -> 2 -> 1：

• 快慢指针停在slow = 3；
• 从3开始反转，得到的后半段是1 -> 2 -> 3；
• 左指针从头开始：1、2、3；
• 右指针从反转后的头开始：1、2、3；
• 当右指针走到最后一个节点3时，左边也恰好走到中间节点，比较完成后right.next = None，循环结束。

偶数长度链表1 -> 2 -> 2 -> 1：

• slow停在第二个2；
• 从第二个2开始反转，得到的后半段是1 -> 2；
• 左指针从头开始：1、2；
• 右指针从反转后的头开始：1、2；
• 右指针走完时，左指针也正好走完对称位置。

所以使用while right:不会漏比较，也不会越界。有些实现会写成while right and left:，也能跑通，但right作为基准更简洁，因为后半段始终不会比前半段更长。

3.3 核心代码实现与逐行解释

我用的语言是 Python，链表节点定义如下：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

最优解完整代码如下：

def isPalindrome(head): if head is None or head.next is None: return True # 第一步：快慢指针找中点 slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 第二步：反转后半段 prev = None cur = slow while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt # 此时 prev 指向反转后的后半段头 # 第三步：双指针比较 left = head right = prev result = True while right: if left.val != right.val: result = False break left = left.next right = right.next # 第四步：恢复后半段链表（可选但推荐） prev2 = None cur = prev while cur: nxt = cur.next cur.next = prev2 prev2 = cur cur = nxt slow.next = prev2 return result

第一步中，while fast and fast.next这个条件保证快指针一次能走两步时才会继续移动。如果链表只有一个节点，fast.next为None，循环不会进入。对于偶数长度，比如1 -> 2 -> 2 -> 1，最终fast会停在None；对于奇数长度，fast会停在最后一个节点。

第二步中，反转后的后半段头是prev。这里有一个点容易绕晕：反转前的slow在反转完成后，它的next已经被改成指向prev之前的节点，所以原来的后半段和前半段的关系已经被切断。比较操作直接在反转后的链上进行就可以了，不用再管原来的slow.next指向哪里。

第三步中，result先假设是True，一旦出现不相等就标记为False并跳出循环。这里没有直接return False，是为了保证后面还能执行恢复链表操作。这是个很重要的工程习惯。

第四步中，我们把prev指向的反转后链表再反转一次，让后半段恢复成原来的顺序，最后通过slow.next = prev2接回原链表。这样输入链表在函数返回后和进入前完全一致。

3.4 复杂度与实测心得

这个解法的时间复杂度是 O(n)，因为每个节点最多被访问常数次：找中点访问一遍，反转访问半遍，比较访问半遍，恢复又访问半遍。空间复杂度是 O(1)，只用了几个指针变量。

我在实际测试中发现，如果链表长度只有 2，比如1 -> 1，流程一样可以跑通。快慢指针停在第二个节点，反转后半段得到1 -> None，比较左节点1和右节点1，随后恢复链表，一切正常。

这里还有一个冷门细节：反转后半段后，原来链表的尾节点的next已经变成了None。恢复时，我们是把prev这个反转链再反转回去，得到的prev2就是原来后半段的头节点，但它的next已经一路指到了原链表的尾节点并结束。因此slow.next = prev2可以把后半段接回去。我写代码时经常在这里犯迷糊，后来养成了一个习惯：直接在纸上画出五个节点的指针变化，画清楚后再写代码，出错率直线下降。

4. 解法三：递归比较法，思路清奇但空间吃亏

4.1 利用函数调用栈从尾部开始比较

除了数组和反转，还有一种思路是利用递归的调用栈天然具备“后进先出”的特性。递归函数可以一直往链表尾部深入，然后在回溯时从尾部开始比较节点值。这就像把递归栈当作了隐式数组，所以在思路上很巧妙。

实现方式是用一个外部变量front保存当前左边的节点。递归函数接收一个当前节点cur，如果cur为空，则返回True。然后先递归处理cur.next，也就是先走到链表末尾。递归返回后，比较front.val和cur.val。如果相等，就让front往后移动一位，并返回True；如果不相等，返回False。

参考实现如下：

class Solution: def isPalindrome(self, head: ListNode) -> bool: self.front = head def dfs(cur): if cur is None: return True if not dfs(cur.next): return False if self.front.val != cur.val: return False self.front = self.front.next return True return dfs(head)

这个代码跑起来没问题，但需要理解递归顺序：先一路走到链尾，再逐步回溯。每次回溯时，cur是从尾向前移动的，而self.front是从头向后移动的，二者正好形成左右对照。

4.2 时间复杂度与空间复杂度

递归解法的时间复杂度同样是 O(n)，每个节点访问一次。但空间复杂度是 O(n)，因为递归调用的深度等于链表长度。系统会在调用栈中为每一层保存上下文，链表越长，占用的调用栈越深。

如果链表很短，比如几十个节点，这种解法完全可行。但如果在生产环境或大规模数据中，链表长度达到上万，递归深度过大会可能导致栈溢出。这也是为什么它更像是“思路展示”，而不是工程推荐方案。

4.3 面试时能说，但别当成主答案

我自己的面试经验是：如果你先讲快慢指针反转后半段的最优解，再补一句“还有一种利用递归栈的另类解法，但空间复杂度是 O(n)，不如刚才那种”，会让人觉得你思路开阔。但如果你把递归解法当成主答案，面试官追问优化时，你就得被迫切换到反转解法。

所以在实际准备过程中，我会把递归解法当作理解回文本质的一种辅助手段，而把快慢指针反转解法当作标准答案。相对数组解法，递归解法的代码更短，但理解成本更高，不太适合作为考场首选。

5. 边界条件与常见问题排查

5.1 空链表和单节点：最容易漏掉的第一道门槛

很多人在写反转解法时，会忘记开头对空链表和单节点链表的判断。如果不处理，后面的快慢指针会出现问题。比如head为空时，直接访问head.next就会报空指针异常。

正确的做法是在函数最前面加上：

if head is None or head.next is None: return True

这里单节点链表按照回文定义应该返回True，因为正序和逆序都是同一个节点。

如果你用的是数组解法，空链表和单节点不会导致代码崩溃，但依然建议统一处理，这样逻辑更清晰。

5.2 快慢指针初始化位置带来的差异

快慢指针的初始化可以有两种习惯：一种是从head开始，另一种是从head.next开始。我推荐统一从head开始，写成：

slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next

这样得到的中点规则比较稳定：偶数长度时slow落在中间偏右，奇数长度时落在正中间。如果你从head.next开始，中点的位置会偏移，直接导致反转后半段的长度不一样，进而影响比较循环。为了避免混淆，我自己刷题时固定使用第一种写法。

如果你发现通过 LeetCode 的测试用例时结果不对，优先检查一下是不是快慢指针初始位置写错了，尤其是复制粘贴旧代码时容易把上一题的写法带过来。

5.3 反转后半段后为什么没有丢节点

一个常见的疑问是：反转后半段之后，原链表从slow到末尾这部分链路已经被破坏，比较两个链表时会不会丢节点？不会。

原因是找完中点后，slow就是后半段的起始节点。反转操作只修改了从slow到末尾这条链上的next指针，前半段从头到slow之前的节点没有动。比较时，左指针从原头部开始，右指针从反转后的后半段头部开始，两条链的长度关系是确定的：偶数长度时两条链等长，奇数长度时后半段链比前半段少一个节点。因此不会丢节点。

5.4 恢复链表真的是可选项吗

从函数功能来看，判断回文只需要返回布尔值，不恢复链表也能通过标准测试。很多刷题平台的判题系统只检查返回值，不会检查输入链表是否被改坏。但真实工程环境不同，函数入参不应该被随意修改。

我在面试复盘时总结过一个习惯：写完判断逻辑后，额外做一次反转恢复。这既是工程素养的表现，也能避免后续题目继续使用这个链表时踩坑。恢复代码就放在比较逻辑后面，把prev指向的链表再反转一次，然后slow.next = prev2。

如果你在线上笔试中时间紧张，可以先不写恢复，等所有逻辑通过后再补上。但建议保留这个意识。

5.5 常见问题速查表

5.6 我自己踩过的一个坑

我第一次写快慢指针反转解法时，把恢复链表逻辑放在了返回之前，但是恢复时用错了变量。我当时直接拿cur去恢复，可cur已经是None，结果链表后半段没接回来，测试用例一跑就出错。

后来我总结出一个简单的检查方法：恢复操作的本质是把当前反转后的链表再反转一遍。当前反转后的链表头是prev，所以恢复时起点必须从prev开始。如果你把头指针搞错了，整个恢复就没有意义。这个坑很隐蔽，尤其是代码长短混杂的时候，建议多打日志或者用短链表实际跑一遍。

6. 从回文链表延伸出去：同类题与面试答题节奏

6.1 字符串回文与链表回文的异同

字符串判断回文很简单，因为字符串天然支持随机访问，直接用双指针从两端向中间靠拢即可。但链表回文多了一个限制：单向链表不能从尾部向前遍历。所以链表版的回文判断才会衍生出反转后半段的需求。

理解这个差异对做同类题很有帮助。比如环形链表、链表中点、链表倒数第 k 个节点，这些题背后共享同一套快慢指针思想。当你能把“回文链表”里的快慢指针拆出来，往后做很多链表题都会顺畅很多。

6.2 同类型题目如何联动

做完回文链表后，我建议紧接着刷这几类题：

• 链表中点：直接把回文链表的前半部分代码抽出来；
• 反转链表：把后半段反转逻辑单独复习；
• 环形链表：同一个fast走两步、slow走一步的模板；
• 合并两个有序链表：锻炼指针拼接能力。

这些题之间不是孤立的，回文链表正好是它们的交叉点。我刷题时不追求数量多，而是追求一题多解和一题多用。把回文链表彻底吃透，比稀里糊涂刷十道简单链表题更有价值。

6.3 面试官想听到什么样的回答

我自己模拟过很多次面试官，也被人当过面试官。面对回文链表，最理想的答题节奏是：

先报数组解法，快速给出正确结果，体现思维清晰。然后主动说“这个空间复杂度是 O(n)，如果要求 O(1) 空间，我还有一个优化方案”。接着讲快慢指针找中点、反转后半段、比较、恢复链表，每一步都把指针变化说清楚。最后补充一句“我比较完会恢复原链表，避免修改入参”。

这套节奏下来，面试官基本能确认你对链表操作是熟练的。相反，如果只背代码，不解释为什么while right:不越界，或者解释不清奇偶长度差异，就会被认为理解不够深入。

我个人体会是，这道题最大的价值不是让面试官看你写代码，而是看你如何在有约束条件下调整方案。实际工程里我们经常遇到“内存吃紧”“不能改原数据”这类限制，能在一个简单题里提前体会这种权衡，后面写复杂系统时会少走很多弯路。如果你也想快速巩固链表基本功，不妨把回文链表当作一个起点，把它反复写到不用看代码就能默写的程度，再往下一个题目进发。