LeetCode 234简单链表 · 综合
回文链表 图解题解
同一条链表，从头读和从尾读都一样？O(1) 空间的做法把两道经典题拼在了一起。
判断一条珠串是否回文，最省空间的办法：先用快慢指针找到中间那颗，把后半段原地反转成一条新链，然后让两根手指分别从原链头部和反转后半链头部同向往前走，逐颗比对——全对就是回文。整个过程是找中点和反转链表两招的合体，只多用几个临时指针，不另开数组。
这道题到底在问什么
判断单链表是否为回文(正读反读一样)。要求 O(1) 额外空间。
- 输入
- 1 → 2 → 2 → 1
- 输出
- true
最优解：一步一步想明白
- 3把值全存进数组、再首尾双指针往中间比，简单，但要 O(n) 额外空间。想做到 O(1) 空间，得在链表本身上动手。
- 4转折：这题其实是 876 找中点 和 206 反转链表 的合体。先快慢找中点，把后半段原地反转，再从原头和反转后的尾两头往中间走逐个比值——全相等就是回文，只花 O(1) 空间。
- 5slow=1, fast=1第一步找中点：slow 走 1 步、fast 走 2 步，都从头出发。下面分开移动看得清楚。
- 6slow 仍在下标0, fast→下标1fast 这一步要走两格，先看第一跳：slow 还停在下标 0，fast 先跨一格到下标 1(第一个 2)。这只是 fast 两跳里的头一跳，还没走完。
- 7slow→下标1, fast→下标2fast 第二跳：fast 再跨一格到下标 2(第二个 2),两跳走完;同时 slow 走 1 步到下标 1(值 2)。fast 把 slow 甩开,领先正好是 slow 走过距离的两倍。
- 8fast.next 为空 → 停第 2 轮：slow 走到下标 2(第二个 2)，fast 想再跨两步就冲出链表(变 null)，循环条件 fast 且 fast.next 不成立、停。slow 此刻把链表分成前半 [1,2] 和后半 [2,1]，后半从 slow 开始。
- 9准备掉头下标2、3第二步反转后半段 [2,1]。从 slow 起设 cur=slow(下标 2)、prev=空。后半只有下标 2、3 两个节点，要把它们之间那根箭头掉头。
- 10下标3 → 下标2先存好 cur.next(下标 3)，再把下标 2→3 那根箭头掉头(变 ←)，让 3 指回 2。然后 prev 前进到 2、cur 前进到 3，继续。
- 11新头 prev = 下标3的1cur 走过下标 3 后变空，反转结束。后半从 2→1 变成 1→2，新头是最后那个 1(下标 3)，记作 prev——它就是双指针比较的右起点。
- 12left=下标0, right=下标3第三步比较：left 从原头(下标 0，值 1)、right 从反转后半的新头(下标 3，值 1)。比第一对：1 等于 1，相等，两个一起往中间走。
- 13left=下标1, right=下标2left 沿正常箭头到下标 1(值 2)，right 沿反转后的箭头到下标 2(值 2)。比第二对：2 等于 2，相等。right 再走就到空，比较即将结束。
- 14left=下标1(值2), right=下标2(值3) → 2≠3 停真换一条非回文 [1,2,3,1] 跑给你看：第一对 1=1 过，第二对 left=2、right=3，2 ≠ 3，这一刻就立即返回 false，不必比完——中途有一对不等，就不是回文。
- 15right 到头 → trueright 走到头(后半比完)，每一对都相等，返回 true。比较只走了半条链，不会越界。
- 18难题往往是基础招式的拼装：找中点 + 反转 + 双指针。熟练的小套路，是解决大问题的积木——这正是「套路模板」的价值。
- 22把这题练到能复述后，去链表专题里迁移：LC143 重排链表同样先找中点、反转后半，再前后交替穿插。不会的地方点右下角问问 AI 助教小欧。
- 25这套「中点 + 反转后半」的骨架不止解回文：LC143 重排链表也是先找中点、再反转后半。先把它从本题里抽出来，下面就是可背模板。
⚠️ 容易写错的地方
✗ 错：比较时走完整条链(while left 且 right)
✓ 对：以后半 right 是否到头为准(while right)
奇数长度时前半比后半多一个，走完整条会越界或多比一次中间值
✗ 错：反转前忘了找中点、或顺序乱了
✓ 对：严格按 找中点 → 反转后半 → 比较 三步
没先定位中点就反转，会把整条链或错误区段反掉，比的位置全错
✗ 错：反转时直接改 cur.next 没先存 nxt
✓ 对：先 nxt = cur.next 再 cur.next = prev
不先存后继，箭头一掉头就找不到下一个节点，链断在半路
完整代码（Python / C++ / Java）
Python
class Solution:
def isPalindrome(self, head):
slow = 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
left, right = head, prev # ③ 左右对撞比较
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return TrueC++
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) { // ① 快慢找中点
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = nullptr; // ② 反转后半段
ListNode* cur = slow;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
ListNode* left = head; // ③ 左右对撞比较
ListNode* right = prev;
while (right) {
if (left->val != right->val) return false;
left = left->next;
right = right->next;
}
return true;
}
};Java
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { // ① 快慢找中点
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null; // ② 反转后半段
ListNode cur = slow;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
ListNode left = head, right = prev; // ③ 左右对撞比较
while (right != null) {
if (left.val != right.val) return false;
left = left.next;
right = right.next;
}
return true;
}
}套路模板 · 中点+反转后半（背下来）
slow = fast = head
while fast and fast.next: # 快慢找中点
slow, fast = slow.next, fast.next.next
prev, cur = None, slow # 反转后半段
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
# 现在 prev 是后半段反转后的新头ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) { // 快慢找中点
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = nullptr; // 反转后半段
ListNode* cur = slow;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur; cur = nxt;
}
// 现在 prev 是后半段反转后的新头ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { // 快慢找中点
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null, cur = slow; // 反转后半段
while (cur != null) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur; cur = nxt;
}
// 现在 prev 是后半段反转后的新头复杂度
时间复杂度
O(n)
找中点扫半条、反转扫半条、比较扫半条，合起来仍是常数倍的 n
空间复杂度
O(1)
只用 slow/fast/prev/cur/left/right 几个指针原地反转，不开数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 回文链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么要做到 O(1) 空间，倒进数组不行吗？+
倒进数组首尾双指针最直观，但要 O(n) 额外空间。面试官常追加 O(1) 约束，逼你在链表本身上做文章：原地反转后半段，只用几个指针。
反转后半段破坏了原链表，要不要恢复？+
面试加分项：比完后把后半段再反转一次拼回去，链表复原、整体仍 O(1) 空间。生产环境若链表共享给别人,必须恢复;只判一次可不恢复。
奇数长度怎么保证不出错？+
快慢指针让 slow 停在后半的头,后半段长度 ≤ 前半。比较以 while right 结束,只走后半长度,正中间那个值天然被跳过,不影响回文判定。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。