随机链表的深拷贝

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

题目描述

给你一个长度为 的链表,每个节点包含一个额外增加的随机指针 random,该指针可以指向链表中的任何节点或 null。

请构造这个链表的深拷贝。深拷贝应该正好由 个全新节点组成,其中每个新节点的值都设为其对应原节点的值。新节点的 next 和 random 指针都应指向复制链表中的新节点,而不能指向原链表中的节点。复制链表中的指针都不应指向原链表中的任何节点。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
      // 每项为 [val, random 指向的索引]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]  // 结构完全相同的全新链表

难点在 random 指针:当你新建一个拷贝节点时,它的 random 该指向哪个新节点?但那个新节点可能还没被创建。这个"引用尚未就绪"的问题,是本题的全部挑战。

思路拆解

暴力解法:哈希表建立「原节点 → 新节点」映射

最直觉的想法:用一个哈希表 Map 记录每个原节点到它对应新节点的映射。分两趟:

1. 第一趟:只按 val 创建所有新节点,存入 Map(此时先不接指针);
2. 第二趟:借助 Map,把每个新节点的 next 和 random 接到"原节点对应指针所指原节点"映射出的新节点上。

为什么哈希表能解决「引用未就绪」？

关键在于先把所有新节点都建出来(第一趟),这样第二趟接指针时,无论 random 指向哪里,那个新节点一定已经存在于 Map 里,直接查表即可。用映射关系表示:

点击展开哈希表解法（清晰易懂，推荐首选）

/**
 * @param {Node} head
 * @return {Node}
 */
function copyRandomList(head) {
  if (!head) return null;

  const map = new Map(); // 原节点 -> 新节点

  // 第一趟：只创建新节点，建立映射
  let cur = head;
  while (cur) {
    map.set(cur, new Node(cur.val));
    cur = cur.next;
  }

  // 第二趟：接好 next 和 random（查表找对应新节点）
  cur = head;
  while (cur) {
    const clone = map.get(cur);
    clone.next = cur.next ? map.get(cur.next) : null;
    clone.random = cur.random ? map.get(cur.random) : null;
    cur = cur.next;
  }

  return map.get(head);
}

哈希表解法的代价

它清晰、好写、时间 ,但需要 的哈希表空间。面试常追问:"能否做到 额外空间?"——这就引出了节点交织法。

最优解法:节点交织(O(1) 额外空间)

不用哈希表,如何知道"原节点对应的新节点是谁"?巧妙的想法:把每个新节点直接插在它对应的原节点后面,让原节点自己"带路"。分三步:

核心思路:复制 → 连 random → 拆分

第一步:交织复制。 遍历原链表,在每个原节点 cur 后面插入它的拷贝 cur':

此时新节点 A' 就紧跟在 A 后面,即 A.next 就是 A'。这条"物理相邻"关系替代了哈希表的映射。

第二步:连接 random。 再遍历一趟,对每个原节点 cur,它的拷贝是 cur.next。若原节点 cur.random 指向 X,那么拷贝的 random 应指向 X 的拷贝,而 X 的拷贝正是 X.next:

第三步:拆分链表。 把交织的链表按奇偶位置拆开,原节点还原成原链表,新节点串成拷贝链表。注意要同时恢复原链表的 next,不能破坏输入。

交互式动画演示

下面用样例链表(值 7 → 13 → 11,random 分别指向 null、7、13)演示节点交织法的三步过程。点击 下一步 观察拷贝节点如何交织插入、random 如何连接、最后如何拆分:

步骤 1 / 11初始状态

原节点拷贝节点↘ random 指针

7

→

13R→o0

→

11R→o1

初始链表：3 个原节点，值为 7 → 13 → 11。random 指针：7→null，13→7，11→13。目标是深拷贝出结构完全相同的新链表。

完整代码(JavaScript)

节点交织法,高亮行为三步的核心操作。

/**
 * // 节点定义
 * function Node(val, next, random) {
 *   this.val = val; this.next = next; this.random = random;
 * }
 * @param {Node} head
 * @return {Node}
 */
function copyRandomList(head) {
  if (!head) return null;

  // 第一步：在每个原节点后插入其拷贝  A -> A' -> B -> B' ...
  for (let cur = head; cur; cur = cur.next.next) {
    const clone = new Node(cur.val);
    clone.next = cur.next; // 拷贝接到 cur 后面
    cur.next = clone;
  }

  // 第二步：连接拷贝节点的 random
  for (let cur = head; cur; cur = cur.next.next) {
    // cur.next 是拷贝；cur.random.next 是「random 所指原节点」的拷贝
    if (cur.random) {
      cur.next.random = cur.random.next;
    }
  }

  // 第三步：拆分，恢复原链表并抽出拷贝链表
  const dummy = new Node(0);
  let copyTail = dummy;
  for (let cur = head; cur; cur = cur.next) {
    const clone = cur.next;   // 拷贝节点
    cur.next = clone.next;    // 恢复原链表的 next
    copyTail.next = clone;    // 拷贝节点接入新链表
    copyTail = clone;
  }

  return dummy.next;
}

复杂度分析

设链表节点数为 。

解法	时间复杂度	空间复杂度	说明
哈希表映射			两趟遍历 + Map 存 个映射
节点交织			三趟遍历,不用额外结构(输出链表不计)
递归 + 哈希			递归栈 + 记忆化 Map,写法简洁

边界与易错点

常见踩坑

1. 空链表:head 为 null 时直接返回 null,否则后续 cur.next.next 会报错。
2. random 为 null 的处理:连接 random 时必须先判断 cur.random 是否存在,为 null 则拷贝的 random 也应为 null(默认即是)。漏判会抛空指针错误。
3. 交织法必须恢复原链表:第三步拆分时,既要抽出拷贝链表,也要把原链表的 next 复原(cur.next = clone.next)。很多人只抽拷贝、忘了还原,导致原输入被破坏。
4. 交织遍历的步长是 cur.next.next:因为每个原节点后面多了一个拷贝,前进两步才是下一个原节点。步长写错会死循环或越界。
5. 哈希表法别忘了 random 也查表:新节点的 random 要指向新节点(map.get(cur.random)),不能直接指向原节点 cur.random,否则就不是深拷贝。
6. 深拷贝 vs 浅拷贝:结果链表的所有指针都不能指回原链表任何节点,这是"深"的核心含义。

简易解题思路(记忆口诀)

一句话记忆:「影子跟班,先复制、再连线、后分家」

把每个原节点想象成一个人,拷贝节点是他的影子跟班,紧跟在身后:

• 先复制(影子入队):让每个人身后都站一个一模一样的影子,队伍变成"人-影-人-影...";这样"谁的影子是谁"一目了然——影子就在本人正后方(cur.next);
• 再连线(影子照抄 random):某人的 random 指向 X,那他影子的 random 就该指向"X 的影子",而 X 的影子正好在 X 后面(cur.random.next),照抄即可;
• 后分家(人影分离):最后把队伍按"人一列、影一列"拆开,人恢复成原队伍(别弄坏),影子单独组成新链表就是答案。

三步口诀:①影子插队 → ②影子照抄 random → ③人影分家。 记住核心画面:"影子紧贴本人站,省掉哈希表;random 照抄'下一个',分家别忘还原人。"

如果图省事、不追求 空间,直接用哈希表两趟法(先建全部新节点、再查表接指针)也是满分答案,而且更好记。