空间解法)
1. 题目理解与第一性原理拆解
回文链表这道题，几乎每个刷LeetCode的人都绕不过去。它出现在Hot100的第23位，面试出镜率极高，尤其是在字节、微软这类喜欢考链表操作的厂子，基本属于必背题。
先看题目本身：给定一个单链表的头节点 head，判断该链表是否为回文链表。回文的意思是正着读和倒着读一样，比如 1 -> 2 -> 2 -> 1 是回文，1 -> 2 -> 3 -> 2 -> 1 也是回文，但 1 -> 2 -> 3 -> 2 就不是。
先说一句大实话：回文数组我们都会做——左右双指针往中间夹逼，O(n)时间O(1)空间就搞定了。但换成链表，问题瞬间变难，因为单链表只能从头往后走，不能从尾往前退，你没法像数组那样直接拿最后一个元素跟第一个元素比。这就是这道题的核心难点所在。
所以解这道题的思路，本质上就是回答一个问题：如何在单向遍历的限制下，实现"从两端向中间"的比较？这也是我当年刷这道题时最大的感悟：LeetCode的链表题，考的往往不是你会不会某一种数据结构，而是你会不会把已知的数组技巧"翻译"成链表能执行的版本。
另外说一个很多人忽略的点：这道题要求的是判断回文，不是找到回文子串，也不是求最长回文，这就意味着我们不需要动态规划或Manacher那种复杂算法，核心考察点就是链表遍历技巧 + 空间复杂度优化意识。题目本身的限制很明确——能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决？这句话才是真正的题眼。LeetCode上这道题的通过率常年徘徊在50%左右，很大一部分人栽在"会做但写不干净"上面——边界条件处理不好、指针移动顺序写错、链表被改坏却不恢复，这些都是扣分重灾区。
下面我把这道题从最直白的解法到最优解全部拆开讲一遍，每段代码都给全，复杂度和边界全部说清楚。
2. 思路一：复制到数组再用双指针——最直白的空间换时间
2.1 核心思路与代码实现
遇到"数组会做、链表不会做"的问题，最朴素的解法就是把链表"打回"数组。遍历一遍链表，把所有节点的值依次存进一个ArrayList或int数组，然后用经典的双指针从两端往中间比较。
public boolean isPalindrome(ListNode head) { List<Integer> vals = new ArrayList<>(); ListNode cur = head; while (cur != null) { vals.add(cur.val); cur = cur.next; } int left = 0, right = vals.size() - 1; while (left < right) { if (!vals.get(left).equals(vals.get(right))) { return false; } left++; right--; } return true; }这段代码非常直白，逻辑上没有任何弯弯绕。时间复杂度O(n)——遍历一次存值，再遍历一次比较，两趟加起来还是O(n)；空间复杂度O(n)，因为额外存了一个长度为n的数组。这个解法在LeetCode上可以直接通过，运行时间大概在4-6ms左右，击败60%左右的提交。
2.2 这个解法的三个隐藏坑
坑一：数值比较不能用 != 而要用 equals。题目给的是 int 类型，但因为存进了 List ，自动装箱后变成 Integer 对象。如果节点的值在 -128 到 127 之间，Integer 有缓存池，用 != 可能碰巧结果正确；一旦超出这个范围，比如值是 128 或 -129，!= 比较的是引用地址而不是数值，结果就会出错。这是LeetCode上非常经典的"看似对了其实错了"的坑。用数组 int[] 存就不会有这个问题，但用 List 一定要用 equals。
坑二：这题节点的 val 是 int，但实际项目里节点值可能是对象，那就还得考虑对象内容比较的语义。好在LeetCode没这么丧心病狂，知道是int就行。
坑三：链表长度为0或1时，直接返回true。空链表和单节点链表天然是回文，代码里 while (left < right) 会自动跳过，所以这个边界在这个解法里其实不用专门处理，但后面几个解法就需要格外小心。
2.3 什么时候用这个解法
我在面试中一般不建议第一反应就甩这个解法，因为面试官接下来一定会问："能不能把空间复杂度优化到O(1)？" 但作为"破冰解法"，先把一个能跑通的版本说出来，再一步步优化，是非常好的面试策略。这比一上来就闷头写最优解，结果写错了反而扣分要稳妥得多。
不过实际刷题时，如果你只是要把题过掉而不是面试，这个解法完全够了。LeetCode官方题解里也把它列为第一种方法，说明它是最容易理解、最不容易出错的版本。
3. 思路二：快慢指针找中点 + 反转后半链表——面试官想听的最优解
3.1 为什么是"找中点 + 反转"的组合拳
既然要O(1)空间，就不能用数组。那怎么在不借助额外空间的情况下实现"两端向中间"的比较？
核心技巧拆成三步：
- 用快慢指针找到链表的中间节点
- 把后半段链表反转
- 同时遍历前半段和反转后的后半段，逐个比较值
举例：1 -> 2 -> 3 -> 2 -> 1。慢指针走到3，然后把后半段 2 -> 1 反转成 1 -> 2，再跟前半段 1 -> 2 -> 3 逐一比较：1=1，2=2，3和null相遇，结束，返回true。
再举例：1 -> 2 -> 2 -> 1。慢指针走到第二个2（或者第一个2，取决于实现），反转后半段，比较，返回true。
3.2 快慢指针找中点的细节
快慢指针的标准写法：
ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }循环结束后，slow 停在链表的"中点"。但这里有个非常容易搞混的细节：链表长度是奇数还是偶数，slow 停的位置不同。
- 奇数长度（如 5 个节点）：slow 正好停在正中间那个节点（第3个）
- 偶数长度（如 4 个节点）：slow 停在第二个中间节点，也就是第3个节点
为什么？因为 fast 每次走两步，slow 每次走一步，fast 走完时 slow 刚好走了 fast 一半的路径。奇数长度时 fast 最后停在最后一个节点，slow 停在正中间；偶数长度时 fast 最后停在 null 上，slow 停在偏右的中间点上。
这个差异直接影响你反转哪一段。我习惯的做法是：记录 slow 的前一个节点，把链表从 prevSlow 处切成两半，然后从 slow 开始反转后半段。这样奇数偶数都不用单独特殊处理。
public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } // 1. 快慢指针找中点，同时记录 slow 的前驱 ListNode slow = head, fast = head, prevSlow = null; while (fast != null && fast.next != null) { prevSlow = slow; slow = slow.next; fast = fast.next.next; } // 2. 切链：从 prevSlow 处断开 prevSlow.next = null; // 3. 反转从 slow 开始的后半段 ListNode secondHalf = reverseList(slow); // 4. 比较两段 ListNode p1 = head, p2 = secondHalf; while (p1 != null && p2 != null) { if (p1.val != p2.val) { return false; } p1 = p1.next; p2 = p2.next; } return true; }注意：奇数长度时（1->2->3->2->1），slow 指向 3，prevSlow 指向第二个2，切链后前半段是 1->2，后半段是 3->2->1。反转后半段变成 1->2->3。比较时 p1=1 与 p2=1 比，p1=2 与 p2=2 比，然后 p2=3 但 p1=null，循环结束返回true。正中间的3不需要跟任何人比，因为它永远等于自己。这个逻辑非常干净。
3.3 反转链表的迭代写法
反转链表本身是另一道经典题（LeetCode 206），这里直接用迭代版：
private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; }核心思想就是三指针原地反转：用 next 先保住后面的节点，再把 cur.next 指向前一个节点，然后整体右移。这个操作必须背熟，因为回文链表、反转链表、两两交换节点这些题全都要用它。
3.4 面试时必问的加分项：恢复链表
LeetCode提交时不会检查链表是否被改动，所以上面的代码能直接过。但如果在面试中，面试官经常追问一个问题："你在判断完之后，链表的结构变了，这样好吗？"
标准回答是：在工程中，函数不应该有副作用，所以我们应该在比较完之后，把后半段再反转一次，拼接回原来的链表。代码就改成：
public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head, fast = head, prevSlow = null; while (fast != null && fast.next != null) { prevSlow = slow; slow = slow.next; fast = fast.next.next; } prevSlow.next = null; ListNode secondHalf = reverseList(slow); // 比较 ListNode p1 = head, p2 = secondHalf; boolean result = true; while (p1 != null && p2 != null) { if (p1.val != p2.val) { result = false; break; } p1 = p1.next; p2 = p2.next; } // 恢复链表 prevSlow.next = reverseList(secondHalf); return result; }注意这里要先把比较结果存到 result 里，不能提前 return，否则后面的恢复代码不会执行。这也是很多人栽过的地方：一找到不相等的节点就 return false，链表就不恢复了。面试时可以主动说出这个细节，绝对加分。
3.5 时间空间复杂度分析
时间上：找中点O(n)，反转后半段O(n/2)，比较O(n/2)，恢复链表O(n/2)，合起来还是O(n)。空间上：只用了几个指针变量，O(1)。这才是真正符合题目要求的解法。
运行时间实测在LeetCode上大约是4-6ms，跟数组解法差不多，但内存占用从44MB左右降到43MB左右——别小看这1MB，在面试的复杂度分析环节，O(1)和O(n)是质的区别。
4. 思路三：递归 + 前后指针——代码最短但隐患最深的解法
4.1 递归怎么模拟"从后往前"
有一种非常巧妙的思路：利用递归的调用栈天然实现"从尾到头"遍历。用一个全局的 frontPointer 从头出发，递归函数一路递归到链表末尾，然后在回溯的过程中，让 frontPointer 跟递归返回的节点逐一对比。
private ListNode frontPointer; public boolean isPalindrome(ListNode head) { frontPointer = head; return recursivelyCheck(head); } private boolean recursivelyCheck(ListNode currentNode) { if (currentNode != null) { if (!recursivelyCheck(currentNode.next)) { return false; } if (currentNode.val != frontPointer.val) { return false; } frontPointer = frontPointer.next; } return true; }执行过程很妙：recursivelyCheck 一路递归到最后一个节点，然后开始回溯。回溯时 currentNode 依次是"最后节点、倒数第二节点……"，frontPointer 从头节点开始，两者逐一对比。比如 1->2->2->1：递归到最后一个1，跟frontPointer的1比，相等，frontPointer移到2，回溯到倒数第二个2，比，相等，frontPointer移到第二个2，继续……
4.2 这个解法最大的坑：栈溢出
我为什么说它"隐患最深"？因为递归深度等于链表长度。LeetCode的测试用例链表最长大概上万节点，递归深度上万层，Java默认栈大小大概512KB到1MB，上万层递归虽然有点悬但往往能过。但如果在真实项目中，链表有几十万甚至上百万节点，这段代码会直接 StackOverflowError 崩掉。
所以这个解法的定位很明确：用来理解"递归即隐式栈"这个思想，但不适合作为工程答案，也不建议在面试中作为主解法。你可以在面试时提一句"还有一种递归的思路"，然后分析它的栈溢出风险，显得你有全局视野。
时间复杂度O(n)，空间复杂度O(n)——因为递归调用栈占用了O(n)的额外空间。从这个角度看，它其实还不如解法一（数组解法），毕竟数组解法至少不会炸栈。
5. 思路四：先反转整条链表再逐一比较——看起来很聪明的陷阱
5.1 错误示范
有一个很容易让人上钩的思路：把链表整体反转，然后两个链表从头开始比较，不就行了？
听上去很合理，但仔细一想就发现问题：反转后的链表会改变原链表的结构。如果你直接把原链表原地反转，比较的时候原来的 head 已经指向最后一个节点了，你拿什么跟反转后的链表比？
有人说那我先复制一份链表再反转啊。可以，但复制一份要O(n)空间，这就回到了解法一的空间复杂度，绕了一大圈并没有更优。还有更隐蔽的bug：值相同的链表不等于结构相同的链表。比如 1->2->1 和 1->2->1 反转后都是 1->2->1，但如果原链表是 1->2->3，反转后是 3->2->1，逐一比较会发现 1 != 3，判定不是回文，这没问题。但假如是 1->2->2->1 呢？反转后是 1->2->2->1，比较全等，判定是回文，也没问题。所以这个思路在"判断回文"这个问题上碰巧是可行的，但它需要额外的O(n)空间来存放反转副本，既没有性能优势，还容易把自己绕晕。
5.2 为什么这个思路值得提一嘴
虽然这个解法不是最优的，但它在面试中的价值在于：它展示了"反转"和"比较"两个操作的组合能力。如果你先说了快慢指针+反转后半段的解法，面试官可能会追问"那如果反转整条链表呢？"你如果能清晰地分析出它的空间问题，说明你对复杂度的理解是到位的。
6. 四种解法对比与面试答题策略
6.1 复杂度对照表
| 解法 | 时间复杂度 | 空间复杂度 | 是否修改链表 | 面试推荐度 |
|---|---|---|---|---|
| 数组复制 + 双指针 | O(n) | O(n) | 否 | 作为引入 |
| 快慢指针 + 反转后半段 | O(n) | O(1) | 是（可恢复） | 最优解 |
| 递归 + 前后指针 | O(n) | O(n) | 否 | 思路补充 |
| 反转整条链表 + 比较 | O(n) | O(n) | 是 | 不推荐 |
6.2 面试现场的答题顺序建议
我自己的习惯是分四步走：
第一步，先提数组解法："这题最简单的方式是遍历链表把值存到数组里，然后左右双指针夹逼，时间O(n)，空间O(n)。"
第二步，立刻补充："但题目要求O(1)空间，所以我们要用快慢指针找中点，把后半段反转，再逐一比较。"
第三步，边写边说关键点："注意快慢指针的循环条件是 fast != null && fast.next != null，这样奇数偶数长度都能正确处理。反转后半段的时候注意保存 next 节点，否则指针就断了。"
第四步，主动说恢复："函数不应该有副作用，判断完之后我会把后半段再反转回来，恢复原链表结构。"
这套流程走下来，面试官基本不会再刁难复杂度问题。我见过很多候选人能写出最优解，但说不出"为什么快慢指针在这个题目里是对的"，这其实是更重要的能力。
6.3 不同语言的实现差异
Java 版本最常见的坑是 Integer 的比较要用 equals，在数组解法里我已经提过了。Python 版本非常简洁，列表存储 + 双指针，或者快慢指针 + 反转都很好写：
def isPalindrome(self, head: ListNode) -> bool: # 快慢指针找中点 slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 反转后半段 prev = None while slow: nxt = slow.next slow.next = prev prev = slow slow = nxt # 比较 left, right = head, prev while right: if left.val != right.val: return False left = left.next right = right.next return TrueC++ 版本要注意释放内存的问题，但LeetCode一般不检查内存泄漏，主要是理解逻辑。Go 版本的链表节点定义和 Java 类似，写起来也很顺手。
7. 常见错误与排查技巧实录
7.1 快指针的循环条件写错导致空指针
这是出现频率最高的bug。很多人写 while (fast.next != null && fast.next.next != null)，或者写成 while (fast != null) 然后 fast.next.next 直接报空指针。
正确的写法是：
while (fast != null && fast.next != null)注意顺序不能反，必须先判 fast != null，再判 fast.next != null，否则偶数长度时 fast 最后指向 null，再访问 fast.next 就是空指针。这个顺序问题在面试中很常见，很多人一紧张就写反了。
7.2 反转后半段时指针丢失
反转链表的经典错误是：
ListNode next = cur.next; cur.next = prev; prev = cur; cur = next;很多人写成 cur = cur.next，结果 cur.next 已经被改成 prev 了，链表就断了，后续遍历全部乱掉。记住：先保存next，再改指针，最后移动。我有个习惯：在纸上画一遍三个指针的移动过程，比硬背代码可靠得多。
7.3 比较时三条链表的边界问题
切链后前半段 head 到 prevSlow，后半段是新链表 secondHalf。比较时注意：
- 如果链表是偶数长度（1->2->2->1），切链后前半段是 1->2，后半段反转后也是 1->2，比较两轮，p1、p2同时为null，退出循环，返回true。
- 如果链表是奇数长度（1->2->3->2->1），切链后前半段是 1->2，后半段反转后是 1->2->3，比较到 p1=null、p2=3 时退出循环。这时因为 p1 先为 null，循环条件 p1 != null && p2 != null 不成立，不会误判。
这里就体现出为什么我用 while (p1 != null && p2 != null) 而不是 while (p1 != null || p2 != null)。用 && 时，奇数长度多出来的中间节点天然被忽略，不需要额外处理。
7.4 恢复链表时的顺序坑
恢复链表时，最常见的错误是提前 return 导致恢复代码不执行。正确的做法是用 result 变量接收结果，最后统一返回。另外，恢复的顺序是：
prevSlow.next = reverseList(secondHalf);这里 secondHalf 在比较过程中可能已经被遍历到链尾，但 reverseList 只依赖 head，无论当前指向哪里，只要传入原来的后半段头节点，都能正确反转并返回新的头。所以比较过程中可以随便移动 p1、p2，不影响恢复操作。
7.5 调试技巧：打印链表结构
如果代码跑不通，我建议写一个辅助函数打印链表：
private void printList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.val + " -> "); cur = cur.next; } System.out.println("null"); }在找中点后打印前半段和后半段，在反转后打印反转结果，在恢复后打印最终链表，一眼就能看出哪一步出了问题。这个习惯帮我解决过很多次棘手的链表bug，比盯着代码死看效率高一万倍。
8. 这道题背后的算法思维与扩展应用
8.1 为什么Hot100里必须有这道题
回文链表在Hot100的地位，不只是因为它本身是道好题，更因为它一把梭了链表问题里三个最核心的操作：遍历、找中点、反转。这三个操作单独拎出来都能出一道题（比如找中点可以用在排序链表里，反转链表本身就是206题），组合在一起就变成了一道经典的"综合应用题"。刷透这道题，等于同时掌握了链表的三个基础操作。
8.2 从回文链表延伸开的同类题
- LeetCode 143 重排链表：也是快慢指针找中点 + 反转后半段 + 交替合并，操作链路和回文链表几乎一模一样。刷完回文链表再去做143，会感觉特别顺手。
- LeetCode 206 反转链表：回文链表的子操作，必须无条件掌握。
- LeetCode 876 链表的中间结点：只考快慢指针找中点，是回文链表的简化版。
- LeetCode 234 变种：判断回文链表但链表节点值可能不是数字，而是字符串或对象，那就需要equals方法而不是==比较，这一点在Java中特别重要。
8.3 回文问题的大类思维
回文判断在字符串领域是一大类问题：LeetCode 125 验证回文串、LeetCode 680 验证回文串II、LeetCode 5 最长回文子串。这些题的通用心法是：回文就是"从两端到中间"的对称结构，核心操作永远是对称位置的比较。链表的难点只是"从右往左"不可访问，所以需要反转或者递归栈来辅助。理解了这一层，你就能把链表题和字符串题串联起来，形成自己的知识网络。
8.4 应用场景映射到实际工作
可能有人觉得链表回文在实际工作中用不到。但换一个角度想：在大数据场景下，你常常需要判断一个单向数据流是否具有对称性。比如操作日志序列里出现了ABA模式的命令操作，或者某个事件流过去一段时间的模式是否对称，这些都可以抽象成"回文判断"问题。而限制条件往往也是不能把整个数据都缓存下来（空间有限），只能用O(1)空间的流式判断思路。工作里虽然不会让你手写一个链表判断回文，但这种"空间有限时如何做对称性扫描"的思维模式，是可以在真实场景中迁移的。
我个人在实际操作中的体会是：这道题最值得练习的并不只是"背出最优解法"，而是在写代码的时候保持对链表结构的清醒认知——每一步操作后，哪些指针还指向原来的节点，哪些已经变了，链表被切成了几段，每一段的头是谁。如果你能一边写一边在脑内完成链表的"可视化"推演，那么链表类的题目基本难不倒你。
最后再分享一个实用的小技巧：如果是刚接触这道题，建议先在纸上画出 1 -> 2 -> 3 -> 2 -> 1 和 1 -> 2 -> 2 -> 1 这两条链表的完整执行过程，分别代入快慢指针找中点、反转后半段、逐一比较三个步骤，把每一步的节点状态写下来。相信我，这个过程花费的二十分钟，比刷十道同类题都管用。
