手帐 Blog

主题

复盘 · LC 206 反转链表（二刷） ​

题目 ​

题意 ​

给定单链表头结点 head，原地反转整条链，返回新的头结点。

  • 例如 1 → 2 → 3 → null 变成 3 → 2 → 1 → null。
  • 空链表、单节点都是合法输入。

边界：head === null；只有一个节点；很长的链（看空间是否炸）。

涉及算法 ​

标签一句话
迭代三指针prev / cur / next，每次把 cur.next 指回 prev
递归先反转尾巴，再把尾巴接到当前节点前

教程对照：12 · 链表基础（精讲题就是 206）。

评价我的解法 ​

相对 7/21 首刷 的「拆进数组再逆序接线」，今天直接改指针——二刷升级成功。

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

javascript
var reverseList = function (head) {
  if (!head) {
    return null;
  }
  let cur = head,
    pre = null,
    next = null;
  while (true) {
    if (cur && cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    cur.next = pre;
    pre = cur;
    cur = next;
    if (cur === null) {
      break;
    }
  }
  return pre;
};

结果正确：空链提前返回；单节点、多节点都能反转，本地也搭了链验证。

  • 时间 O(n)，空间 O(1)——已是标准量级。
  • 优点：核心动作对——先存 next，再 cur.next = pre，再推进；返回 pre 当新头。
  • 糙点：
    1. while (true) + 末尾 break 等价于 while (cur)，多一层噪音。
    2. next 的赋值写成 if (cur && cur.next) 分支；循环里 cur 本就不为 null，直接 next = cur.next 即可。
    3. 空链的 if (!head) return null 可省略——while (cur) 自然返回 pre === null。

小结：从 O(n) 数组法切到 O(1) 三指针，说明 12 的精讲已经能默写骨架；剩下是把循环写成教科书形态。

最佳题解 ​

迭代三指针（教程同款）：

javascript
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};
  • 时间 O(n)，空间 O(1)。
  • 与你今天写法同构，只是循环条件更干净；面试口述就按这四行。

关联题目 ​

题为何相关
92. 反转链表 II区间反转，仍是三指针
234. 回文链表进阶解要反转后半段
25. K 个一组翻转链表206 的分组加强版

一句话带走 ​

反转链表二刷 = 先存 next，再掉头，再前进；循环写成 while (cur) 即可默写。