手帐 Blog

主题

复盘 · LC 234 回文链表 ​

题目 ​

题意 ​

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

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

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

涉及算法 ​

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

教程对照：12 · 链表基础 练习清单（234：找中点 + 反转后半 + 比较）；反转子步骤见同篇 206。

评价我的解法 ​

思路：与当天 206 同款——拆开 next、节点推进数组，再用首尾下标比 val。

我的代码（摘自 234-回文链表/index.js）：

javascript
var isPalindrome = function (head) {
  if (head === null) {
    return false;
  }
  let isHuiWen = true;
  const NodeArr = [];
  while (true) {
    if (!head) {
      break;
    }
    const tmpHead = head;
    const tmpNext = head.next;
    tmpHead.next = null;
    NodeArr.push(tmpHead);
    head = tmpNext;
  }

  for (let i = 0; i < NodeArr.length / 2; i++) {
    const j = NodeArr.length - i - 1;
    if (NodeArr[i].val !== NodeArr[j].val) {
      isHuiWen = false;
      break;
    }
  }
  return isHuiWen;
};

主流程能过：非空链、奇偶长度、单节点都对；首尾夹逼写法清晰。

  • 时间 O(n)，空间 O(n)。
  • 优点：和 206 共用「拆成数组」心智，夹逼段一眼能懂。
  • 糙点 / 坑：
    1. head === null 返回 false：空链通常视为回文（应 true）。本题约束一般是 n ≥ 1，LeetCode 可能测不到，但边界口述要说对。
    2. 没必要掐断 next：本题只比 val，推 head.val（或只存引用不改链）即可；改结构增加干扰，也破坏原链。
    3. 同 206：while (true)、拼音命名；发现不等可直接 return false，不必 isHuiWen 标志。
  • 进阶 O(1) 空间仍要「中点 + 反转后半」——今天这版是合理的「先 AC」。

最佳题解 ​

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. 前半 vs 反转后的后半
  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)。
  • 奇数长度时中点只在前半，后半更短，while (p2) 自然跳过中点。
  • 若面试要求不破坏原链，比较完再把后半反转回去即可。

更省事的「能过」写法（比今天少改结构）：只把 val 推进数组再夹逼。

关联题目 ​

题为何相关
206. 反转链表234 的子程序；今天两题写法同源
876. 链表的中间结点快慢指针找中点
5. 最长回文子串回文直觉（字符串侧）

一句话带走 ​

回文链表：数组夹逼能过，别无谓拆链；满分是「中点 + 反转后半 + 比较」。