复盘 · LC 138 随机链表的复制

题目

• 题号：LeetCode 138
• 名称：随机链表的复制（Copy List with Random Pointer）
• 难度：Medium
• 链接：leetcode.cn/problems/copy-list-with-random-pointer
• 今日代码：138-随机链表的复制/index.js

题意

深拷贝一条特殊链表：每个结点除 next 外还有 random，可指向链表中任意结点或 null。返回新链表头，新旧结点互不共享引用。

• 拷贝的是结构（值 + next/random 拓扑），不是只抄 val。
• random 可指向自己、前方、后方或空。

边界：空链、单结点 random 指自己、random 全 null、交叉乱指。

涉及算法

标签	一句话
哈希映射	旧结点 → 新结点；两遍扫：先建点，再接 next/random
交错插入（进阶）	旧→新→旧→新 织在一起，用邻接关系映射 random，再拆链，O(1) 额外空间

教程对照：12 · 链表基础 / 13 · 链表进阶（深拷贝 + 额外指针，哈希是标准入口）。

评价我的解法

我的代码（摘自 138-随机链表的复制/index.js，不含本地测例）：

var copyRandomList = function (head) {
  let cur = head,
    next = null,
    i = 0,
    preNew = null;
  let newHead = null;
  let nodeArr = [];
  let newArr = [];
  while (cur) {
    if (cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    const newNode = new RandomNode(cur.val, null, cur.random);
    if (preNew) {
      preNew.next = newNode;
    }
    nodeArr.push(cur);
    newArr.push(newNode);
    if (i === 0) {
      newHead = newNode;
    }
    preNew = newNode;
    cur = next;
    i++;
  }

  cur = newHead;
  next = null;
  i = 0;

  while (cur) {
    if (cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    const random = cur.random;
    if (random) {
      let j = 0;
      for (j = 0; j < nodeArr.length; j++) {
        if (nodeArr[j] === random) {
          cur.random = newArr[j];
        }
      }
    }
    cur = next;
  }

  return newHead;
};

能 AC：先沿 next 建出新链，并用平行数组记住「旧下标 ↔ 新结点」；第二遍把暂存的旧 random 引用按数组下标改成新结点。

• 时间 最坏 O(n²)（每个 random 线性扫 nodeArr），空间 O(n)——能过，但不是面试默认满分。
• 对在哪：抓住了「random 先挂旧引用、再重映射」；空 random 自然保留；本地有小链测例。
• 糙在哪：
  1. 用双数组 + 下标查找，等价于手写哈希，却丢掉了 Map 的 O(1) 查找。
  2. 命中后没 break，会空跑完整个数组。
  3. next 的 if/else 仍偏碎；LeetCode 模板结点是 _Node，本地 RandomNode 仅测例用即可。

思路方向对，下一步换成 Map 即可把复杂度压到标准解。

最佳题解

哈希表两遍（推荐默写）：

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function (head) {
  if (!head) return null;
  const map = new Map();
  let cur = head;
  while (cur) {
    map.set(cur, new _Node(cur.val));
    cur = cur.next;
  }
  cur = head;
  while (cur) {
    const copy = map.get(cur);
    copy.next = cur.next ? map.get(cur.next) : null;
    copy.random = cur.random ? map.get(cur.random) : null;
    cur = cur.next;
  }
  return map.get(head);
};

• 时间 O(n)，空间 O(n)。
• 为何更优：旧→新一次查表；next/random 统一接线，无下标扫描。

进阶口述（O(1) 额外空间）：先在每个旧结点后插入拷贝结点 → 用 old.next.random = old.random.next 设拷贝的 random → 再拆成两条链。面试先讲 Map，再提织链加分。

关联题目

题	为何相关
133. 克隆图	同款「旧→新 Map + 深拷贝」
148. 排序链表	链表结构改造，另一类中等题
430. 扁平化多级双向链表	额外指针（child）要一并处理

一句话带走

随机链表深拷贝：先 Map 建完全部新结点，再扫一遍接 next/random——别用双数组线性搜下标。