234. 回文链表 (Easy)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/palindrome-linked-list/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
示例：
- 输入：head = [1,2,2,1]
- 输出：true
- 输入：head = [1,2]
- 输出：false
进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决？
题目详细分析
- 数据范围： 链表中节点数目在 [1, 10^5] 范围内，节点值在 [0, 9] 范围内
- 输入特征： 单链表，只能从头到尾单向遍历，不能反向遍历
- 核心约束： O(1) 空间复杂度的进阶要求意味着不能用数组存储整个链表的值
- 隐藏条件： 回文判断本质是「首尾对称比较」，但单向链表无法直接从尾到头访问
- 边界条件： 只有一个节点的链表是回文、两个相同值的节点是回文、偶数个节点和奇数个节点的处理差异
小白版直白理解
回文就是正着读和倒着读都一样，比如 “上海自来水来自海上”。链表版的回文判断就像一串珠子，要检查颜色是不是对称的。
因为链表只能从前往后走，不能从后往前走，所以想了个办法：先找到中间的那颗珠子，然后把后半段链子掉个头，这样就能从两端往中间一颗一颗对比了。
解题思路
思路一：快慢指针找中点 + 反转后半部分（推荐）
为什么这样想： 回文需要比较对称位置的值。数组可以用双指针从两端向中间移动，但链表不支持反向遍历。所以我们将后半段链表反转，这样就能用两个指针分别从前半段和后半段的起点开始，向中间移动比较。
关键洞察： 快慢指针找中点时，快指针走两步、慢指针走一步。结束时，如果节点数为奇数，慢指针正好在中间节点；如果为偶数，慢指针在中间偏右。我们需要的是后半段的起点，所以直接让慢指针作为后半段起点即可。
def isPalindrome(head):
"""快慢指针找中点 + 反转后半部分"""
if not head or not head.next:
return True
# 1. 快慢指针找中点（slow 最终指向后半段的起点）
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. 反转后半部分链表
prev = None
cur = slow
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
# 3. 比较前半部分和反转后的后半部分
left, right = head, prev
while right: # 后半段可能更短（奇数节点时）
if left.val != right.val:
return False
left = left.next
right = right.next
return True思路二：数组辅助法
思路讲解： 先遍历一遍链表，将节点值依次存入数组。然后在数组上用双指针从头尾向中间比较。思路非常简单直观，但是需要 O(n) 的额外空间，不满足进阶要求。
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思路三：递归法
思路讲解： 利用递归栈实现从后往前访问链表的效果。设置一个全局指针从前往后走，递归函数走到链表末尾后开始回溯，每次回溯时比较全局指针的值和当前递归节点的值。
def isPalindrome(head):
"""递归法"""
front = head
def check(node):
nonlocal front
if not node:
return True
# 递归到末尾，回溯时进行比较
if not check(node.next):
return False
# 比较对称位置
if front.val != node.val:
return False
front = front.next
return True
return check(head)易错点
- 奇数/偶数节点处理： 奇数节点时中间节点不需要参与比较（前后各半），用
while right而不是while left and right可以自然处理 - 反转后链表结构改变： 函数返回后原链表结构已被改变，虽然本题不要求恢复，但在工程中需要注意
- 快慢指针起始： 有些写法将 fast 初始化为
head.next，这会影响中点的位置，务必保持一致 - 空链表和单节点： 空链表或只有一个节点时直接返回 True
- 比较终止条件： 用反转后的后半段作为遍历依据，不要用前半段，因为前半段可能更长
框架提炼
回文链表三步模板： 快慢找中点 + 反转后半 + 逐一比较。
# 1. 找中点
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. 反转后半
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
# 3. 比较
left, right = head, prev
while right:
if left.val != right.val: return False
left, right = left.next, right.next这种「先分割，再处理」的套路也适用于其他需要对称操作的链表问题。
关联题目
- 206-反转链表 — 本题的基础操作，回文判断需要先反转后半段
- 141-环形链表 — 同样使用快慢指针技巧
- 876-链表的中间结点 — 快慢指针找中点的专项练习