手帐 Blog

主题

复盘 · LC 206 反转链表 ​

题目 ​

题意 ​

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

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

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

涉及算法 ​

标签一句话
迭代三指针prev / cur / next，每次把 cur.next 指回 prev
递归先反转尾巴，再把尾巴接到当前节点前
辅助数组先拆成节点数组，再按逆序重接（能过，空间差）

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

评价我的解法 ​

思路：遍历时把每个节点的 next 掐断，推进数组；再从前往后把 NodeArr[i].next = NodeArr[i - 1]，返回数组末尾当新头。

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

javascript
var reverseList = function (head) {
  if (head === null) {
    return null;
  }
  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; i++) {
    if (i === 0) {
      continue;
    }
    NodeArr[i].next = NodeArr[i - 1];
  }
  return NodeArr[NodeArr.length - 1];
};

结果正确，空链有提前返回；单节点时 for 不接线，返回自己，也对。

  • 时间 O(n)，空间 O(n)（整条链进数组）。
  • 优点：步骤拆开好懂——「先拆、再反着接」；不容易丢指针。
  • 糙点：
    1. while (true) + 内层 break 等价于 while (head)，多一层噪音。
    2. 命名 NodeArr 宜用 nodeArr；tmpHead 其实就是当前节点。
    3. 面试默认期望 O(1) 额外空间 的三指针迭代；数组法会被追问「能不能原地」。
  • 本地测例用了 next: undefined，靠 !head 碰巧能停；题面约定是 null，写测例时建议统一。

最佳题解 ​

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

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)。
  • 每次只动一个箭头：先存 next，再回头指 prev，三人一起往前挪。空链时 prev 仍是 null，不用单独 if。

面试口述顺序：画图 → 三指针循环 → 提一句递归也能写但栈深 O(n)。

关联题目 ​

题为何相关
92. 反转链表 II区间反转，206 的局部版
234. 回文链表找中点后要反转后半段
25. K 个一组翻转链表反转是子程序，Hard 里反复调用

一句话带走 ​

反转链表：先画三指针；数组能 AC，面试要能默写 O(1) 空间的 prev/cur/next。