手帐 Blog

主题

复盘 · LC 234 回文链表（二刷） ​

题目 ​

题意 ​

判断单链表节点值是否构成回文（正着读和反着读一样）。

  • 例如 1 → 2 → 2 → 1 为 true；1 → 2 为 false。
  • 进阶：O(n) 时间、O(1) 额外空间。

边界：空链 / 单节点（true）；奇数长度中点；偶数长度对半比较。

涉及算法 ​

标签一句话
转数组再双指针值进数组，左右夹逼——空间 O(n)，好写
快慢指针 + 反转找中点 → 反转后半 → 与前半逐个比

教程对照：12 · 链表基础 练习清单（234）；反转子步骤见同篇 206。

评价我的解法 ​

相对 7/21 首刷 的「拆进数组夹逼」，今天改成给节点挂 pre 做成双向再首尾比——能 AC，但仍未到进阶 O(1) 标准解。

我的代码（摘自 234-回文链表-二刷/index.js，不含本地测例）：

javascript
var isPalindrome = function (head) {
  if (!head) {
    return false;
  }
  if (!head.next) {
    return true;
  }

  let pre = null,
    next = null,
    cur = head;
  while (true) {
    if (cur && cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    cur.pre = pre;

    pre = cur;
    cur = next;
    if (!cur) {
      break;
    }
  }
  let last = pre;
  while (head && last) {
    if (head === last) {
      break;
    }
    if (head.val !== last.val) {
      return false;
    }
    head = head.next;
    last = last.pre;
  }
  return true;
};

主流程能过：奇偶长度、对称用例本地也过了。

  • 时间 O(n)，空间 实质 O(n)（每个节点多一个 pre），且改坏了结构；内存约 13% 档符合预期。
  • 优点：首尾夹逼直觉清楚；中点用 head === last 提前停，奇数长度处理对。
  • 糙点 / 坑：
    1. !head 返回 false：空链通常视为回文（应 true）——首刷就标过，二刷仍在。
    2. 偶数长度时指针会「交叉」多比几轮，结果碰巧对，但不是干净模板。
    3. 改输入 + 额外字段，面试不如「只存 val 数组」干净，更不如「中点 + 反转后半」。
    4. 今天已经会写 206 原地反转，却没用在 234 上——缺口就在这。

小结：工具从数组换成双向指针，空间量级没变；进阶目标仍是 876 找中点 + 206 反转后半 + 比较。

最佳题解 ​

O(1) 额外空间（找中点 + 反转后半 + 比较）：

javascript
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  if (!head || !head.next) return true;

  // 1. 快慢指针找中点（偶数长度时 slow 落在左半末）
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. 反转后半
  let prev = null;
  let cur = slow.next;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }

  // 3. 前后比较
  let p1 = head;
  let p2 = prev;
  while (p2) {
    if (p1.val !== p2.val) return false;
    p1 = p1.next;
    p2 = p2.next;
  }
  return true;
};
  • 时间 O(n)，空间 O(1)（不计递归栈；迭代版）。
  • 与今天 206 二刷打通：后半段就是默写一遍反转。

关联题目 ​

题为何相关
206. 反转链表后半段反转子程序
876. 链表的中间结点快慢找中点
9. 回文数回文判定另一载体

一句话带走 ​

回文链表进阶 = 中点 + 反转后半 + 比 val；别再用挂 pre 或整链进数组搪塞 O(1)。