回文链表

更新: 7/5/2026 字数: 0 字时长: 0 分钟

LeetCode 234. Palindrome Linked List

题目描述

给你一个单链表的头结点 head，请你判断该链表是否为 回文链表。如果是，返回 true；否则，返回 false。

所谓「回文」，就是正着读和倒着读完全一样，例如 1→2→3→2→1 或 1→2→2→1。

进阶要求：你能否用时间复杂度和空间复杂度解决此题？

示例：

输入：head = [1,2,2,1]
输出：true

输入：head = [1,2,3,2,1]
输出：true

输入：head = [1,2]
输出：false

快慢指针找中点

思路拆解：从暴力到最优

想法一：倒进数组，双指针对比（暴力解法）

链表不能像数组那样从尾往前走，最直接的想法就是：把所有值倒进数组，然后用头尾双指针向中间夹逼，逐个比较是否相等。

点击展开暴力解法

function isPalindrome(head) {
  const arr = [];
  let p = head;
  while (p) {            // 1) 把值全部倒进数组
    arr.push(p.val);
    p = p.next;
  }
  let i = 0, j = arr.length - 1;
  while (i < j) {        // 2) 头尾双指针向中间夹逼比较
    if (arr[i] !== arr[j]) return false;
    i++;
    j--;
  }
  return true;
}

时间：，遍历一遍 + 比较一遍。
空间：，额外开了一个数组。

它能过，但没满足进阶的常数级空间要求——因为借用了数组。

为什么暴力不够好？

数组解法之所以简单，是因为它把「不能倒着走」的问题用额外空间绕开了。但链表其实有个杀手锏：指针可以 O(1) 反向。如果我们把链表的后半段就地反转，就能同时从「前半段头部」和「后半段头部（原尾部）」向中间走，不再需要数组。这正是把空间从降到的关键。

想法二：快慢指针找中点 + 反转后半段（最优解法）

要做到空间，核心是在链表本身上动手。整个过程分三步：

核心思路

找中点 → 反转后半段 → 双指针对比 三步走：

快慢指针找中点：slow 走一步、fast 走两步，当 fast 到末尾时，slow 恰好停在中间（或后半段起点）。
反转后半段：从 slow 开始，把后半段链表就地反转，得到一条从原尾部指向中间的链。
双指针对比：一个指针从头开始，一个指针从反转后的后半段头开始，逐个比较值是否相等。全部相等就是回文。

为什么这样想？因为回文的本质是「前半段 == 后半段的逆序」。既然我们没法直接倒着读后半段，那就把它物理反转，让它变得可以正着读——这样两段就能同向逐个比对了。

反转后半段，两头向中间对比

关键操作 1：快慢指针找中点

slow 一次走一步，fast 一次走两步。当 fast 走到末尾（fast === null 或 fast.next === null）时，slow 恰好在中间。

对偶数长度（如 1,2,2,1），slow 停在后半段的第一个节点；
对奇数长度（如 1,2,3,2,1），slow 停在正中间节点。这个正中间节点属于哪半段都无所谓，因为它不影响对比结果。

关键操作 2：反转后半段

从 slow 开始，用经典的三指针（prev、cur、next）就地反转。反转完成后，prev 指向后半段的新头（也就是原链表的尾节点）。

动态演示

下面的动画完整演示了对 [1,2,3,2,1] 判断是否回文的三步全过程——找中点、反转后半段、双指针对比：

步骤 1 / 13① 快慢指针找中点

slow / p1fastp2（后半段头）已确认相等

slowfast

→

初始化：slow、fast 都指向头结点，准备用快慢指针找中点。

完整代码（JavaScript）

/**
 * @param {ListNode} head
 * @return {boolean}
 */
function isPalindrome(head) {
  if (!head || !head.next) return true; // 空链表 / 单节点，天然回文

  // 1) 快慢指针找中点，slow 最终停在中间（后半段起点）
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2) 反转后半段（从 slow 开始）
  let prev = null, cur = slow;
  while (cur) {
    const next = cur.next; // 先存下一个，防止断链
    cur.next = prev;       // 反转指针
    prev = cur;            // prev 前移
    cur = next;            // cur 前移
  }
  // 此时 prev 是反转后后半段的头（原尾节点）

  // 3) 双指针对比：p1 从头走，p2 从后半段头走
  let p1 = head, p2 = prev;
  while (p2) {             // 后半段更短或等长，以 p2 为终止条件
    if (p1.val !== p2.val) return false;
    p1 = p1.next;
    p2 = p2.next;
  }
  return true;
}

进阶：对比后恢复链表原状

工程实践中，若不希望函数修改传入的链表结构，可以在对比完成后再把后半段反转回去，恢复原链表。做法就是把「反转后半段」的代码原样再执行一次即可。这在多线程或后续还要复用该链表的场景下很重要。

// 对比结束后，把 prev 开头的后半段再反转一次即可复原
function reverse(node) {
  let prev = null, cur = node;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

复杂度分析

设链表长度为。

解法	时间复杂度	空间复杂度	说明
倒进数组 + 双指针			借助额外数组，不满足进阶
快慢指针 + 反转后半段			只用常数个指针，满足进阶
递归（利用系统栈）			递归栈深度为，空间不占优

为什么最优解是时间、空间？ 找中点遍历半程、反转后半段遍历半程、对比再遍历半程，加起来仍是常数倍的，即；整个过程只用了 slow、fast、prev、cur、next 等固定几个指针变量，与链表长度无关，所以是。

边界与易错点

易错点

空链表和单节点。head 为 null 或只有一个节点时，直接返回 true（天然回文）。开头的 if (!head || !head.next) return true; 已覆盖。
反转时先存 next。反转指针 cur.next = prev 之前，必须先用 const next = cur.next 把下一个节点存下来，否则链就断了、找不回后面的节点。这是链表反转的通用铁律。
对比的终止条件用后半段。奇数长度时，前半段会比后半段多一个（中间节点），所以循环用 while (p2)（后半段走完即止）而不是 while (p1)，否则奇数链表会多比一次、出错。
快慢指针的循环条件。while (fast && fast.next) 同时判断 fast 和 fast.next，缺一个都会在奇偶长度切换时出现空指针错误。
中间节点归属无所谓。奇数长度时 slow 停在正中间，把它算进后半段一起反转也没关系——它是回文的对称轴，比不比都相等。
是否需要复原链表。本题只要求返回布尔值，可以不复原；但若面试官强调「不能破坏原链表」，记得对比后再反转回去（见上面的进阶）。

简易解题思路（记忆口诀）

「快慢找中点，后半翻个面；两头向中间，逐个比一遍。」

拆开记：

口诀	对应操作
快慢找中点	`slow` 走一步、`fast` 走两步，快到头时慢在中间
后半翻个面	从 `slow` 起，用三指针把后半段就地反转
两头向中间	一个指针从头走，一个从反转后的后半段头走
逐个比一遍	两指针同步前进，值不等就返回 `false`，走完全等就是回文

一句话记住本质：回文就是「前半段 == 后半段倒过来」——既然不能倒着读，那就把后半段真的翻过来，再两头对着比。

回文链表 ​

题目描述 ​

思路拆解：从暴力到最优 ​

想法一：倒进数组，双指针对比（暴力解法） ​

想法二：快慢指针找中点 + 反转后半段（最优解法） ​

关键操作 1：快慢指针找中点 ​

关键操作 2：反转后半段 ​

动态演示 ​

完整代码（JavaScript） ​

复杂度分析 ​

边界与易错点 ​

简易解题思路（记忆口诀） ​