随机链表的复制（LeetCode 138）——哈希表映射与两遍遍历深拷贝实战解析

本篇基于「算法通关手册（AlgoNote）」题解库中的 0138. 随机链表的复制题解 展开。围绕「带随机指针的链表深拷贝」这一高频面试题，详细拆解哈希表「旧节点 → 新节点」映射 + 两遍遍历的解法思路、代码实现与复杂度分析，并结合仓库中的链表与哈希表源码级实现深入原理。读完你将掌握：如何为带 random 指针的链表构造完全独立的新链表，以及哈希表在「引用映射」场景下的核心价值。

1. 题目背景与问题本质

1.1 题目描述

题目链接：0138. 随机链表的复制 - 力扣

给定一个链表的头节点 head，链表中的每个节点除了指向下一个节点的 next 指针之外，还额外包含一个随机指针 random。该 random 指针可以指向链表中的任意节点，也可以指向空节点 null。

要求：将该链表进行深拷贝（Deep Copy），并返回复制后新链表的头节点。

1.2 数据范围说明

• 链表中节点数量满足 $0 \le n \le 1000$。
• 每个节点的值满足 $-10^4 \le Node.val \le 10^4$。
• Node.random 的取值要么为 null，要么为链表中的某个节点。

1.3 示例分析

• 示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

[[7,null],[13,0],...] 的书写格式中，内层列表的第二个元素表示 random 指针指向的节点下标（从 0 开始），例如 [13,0] 表示值为 13 的节点的 random 指向下标为 0 的节点（即值为 7 的节点）。拷贝结果与原链表结构完全一致，但所有节点都是新建的。

• 示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

1.4 为什么不能直接复制 next 链

表面上看，这只是一个普通的链表复制问题：先按 next 新建一条链表即可。但难点在于 random 指针：

• 在复制过程中，random 指向的目标节点可能尚未创建（例如它指向链表后方的节点）；
• random 也可能指向自身或前方节点，如果用「边遍历边按位置创建」的方式，很难保证 random 最终指向的是新链表中的对应节点，而不是旧链表中的节点；
• 如果简单地让新节点的 random 直接指向旧节点，那就变成了浅拷贝，修改旧链表会影响新链表，不符合题目要求。

因此，核心矛盾在于：如何在 random 目标节点尚未生成、或位置关系任意的情况下，仍然能精准建立「旧节点 → 新节点」的一一对应关系。

2. 解法核心：哈希表建立「旧节点 → 新节点」映射

2.1 思路总览

解决上述矛盾的关键，是借助哈希表（Python 中即 dict）在旧链表与新链表之间建立一一映射：

1. 第一遍遍历：只做「节点创建 + 映射登记」。遍历原链表，为每个旧节点 curr 创建一个值相同的新节点 Node(curr.val, None, None)，并以 旧节点: 新节点 为键值对存入哈希表 node_dict。此时先不设置任何指针。
2. 第二遍遍历：根据哈希表补齐新链表的指针关系。再次遍历原链表，对每个旧节点 curr：
   • 如果 curr.next 不为空，则让 node_dict[curr].next 指向 node_dict[curr.next]；
   • 如果 curr.random 不为空，则让 node_dict[curr].random 指向 node_dict[curr.random]。
3. 遍历结束后，返回 node_dict[head]，即新链表的头节点。

因为第一遍遍历结束后，所有新节点都已经创建完成，第二遍遍历时无论 random 指向哪个旧节点，都能通过哈希表在 $O(1)$ 时间内找到与之对应的新节点。这就是整个算法的精妙之处：先登记、后连线。

2.2 参考代码（哈希表 + 两遍遍历）

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None

        node_dict = dict()
        curr = head

        # 第一遍遍历：创建新节点，登记 旧节点 -> 新节点 映射
        while curr:
            new_node = Node(curr.val, None, None)
            node_dict[curr] = new_node
            curr = curr.next

        curr = head
        # 第二遍遍历：借助哈希表补齐 next 与 random 指针
        while curr:
            if curr.next:
                node_dict[curr].next = node_dict[curr.next]
            if curr.random:
                node_dict[curr].random = node_dict[curr.random]
            curr = curr.next

        return node_dict[head]

说明：题目给定的节点类 Node 构造签名为 Node(val, next, random)，因此新建节点时写作 Node(curr.val, None, None)。如果是在本地调试，需要自行定义该节点类。

2.3 代码逐行剖析

• if not head: return None：空链表直接返回 None，避免后续对 None 取属性报错，这也是边界情况的兜底处理。
• 第一遍 while curr 循环：只做两件事——new_node = Node(curr.val, None, None) 创建新节点、node_dict[curr] = new_node 登记映射。此时新节点之间没有任何链接关系，全部是「孤儿节点」。
• 第二遍 while curr 循环：node_dict[curr].next = node_dict[curr.next] 这一行完成了 next 指针的复制。由于第一遍已经遍历完所有节点，curr.next 一定已经在哈希表中，取出的 node_dict[curr.next] 就是对应的新节点，不存在「目标节点尚未创建」的问题。
• 同理，node_dict[curr].random = node_dict[curr.random] 完成 random 指针的复制，无论 random 指向链表中任何一个节点（包括头节点、自身、尾部节点），都能通过哈希表 $O(1)$ 命中。
• return node_dict[head]：返回新链表的头节点。这里返回的是新节点而非旧节点，满足深拷贝要求。

2.4 复杂度分析

• 时间复杂度：$O(n)$。两次遍历链表，每次遍历 $n$ 个节点；哈希表的插入与查找操作平均时间复杂度均为 $O(1)$，因此总时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。哈希表 node_dict 中需要存储 $n$ 对「旧节点 → 新节点」的映射，再加上新建的 $n$ 个节点本身，整体空间开销为 $O(n)$。

2.5 正确性验证：完整可运行示例

为了验证算法正确性，可以在本地构建一个带 random 指针的链表并跑通拷贝流程。下面给出一个可以直接运行的最小验证程序：

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copy_random_list(head):
    if not head:
        return None
    node_dict = dict()
    curr = head
    while curr:
        node_dict[curr] = Node(curr.val, None, None)
        curr = curr.next
    curr = head
    while curr:
        if curr.next:
            node_dict[curr].next = node_dict[curr.next]
        if curr.random:
            node_dict[curr].random = node_dict[curr.random]
        curr = curr.next
    return node_dict[head]

def print_list(head):
    """按 (val, random_val) 打印链表，便于核对拷贝结果。"""
    cur = head
    while cur:
        r = cur.random.val if cur.random else None
        print(f"({cur.val}, {r})", end=" -> ")
        cur = cur.next
    print("None")

# 构造：7 -> 13 -> 11 -> 10 -> 1
# random 指向：7.random=None, 13.random->7(下标0), 11.random->1(下标4),
#             10.random->11(下标2), 1.random->7(下标0)
n0 = Node(7)
n1 = Node(13)
n2 = Node(11)
n3 = Node(10)
n4 = Node(1)
n0.next, n1.next, n2.next, n3.next, n4.next = n1, n2, n3, n4, None
n0.random, n1.random, n2.random, n3.random, n4.random = None, n0, n4, n2, n0

clone = copy_random_list(n0)
print("原链表:")
print_list(n0)
print("拷贝链表:")
print_list(clone)
print("拷贝头节点是否为新节点:", clone is not n0)

运行结果应输出：

原链表:
(7, None) -> (13, 7) -> (11, 1) -> (10, 11) -> (1, 7) -> None
拷贝链表:
(7, None) -> (13, 7) -> (11, 1) -> (10, 11) -> (1, 7) -> None
拷贝头节点是否为新节点: True

其中「拷贝头节点是否为新节点: True」验证了新链表头节点与旧链表头节点不是同一个对象，符合深拷贝的定义。

3. 原理纵深：从仓库源码看链表与哈希表

本题是「链表」与「哈希表」两大知识点的经典结合。仓库 AlgoNote 对这两个主题都有成体系的讲解与实现，可作为深度阅读入口。

3.1 链表：从单向链表到带随机指针的链表

链表基础文档 中指出，链表是线性表的链式存储实现：每个「链节点」除了存放数据元素本身，还要额外存储一个指向后继节点的指针。在 链表源码实现 中可以看到标准的节点类定义：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

本题的节点类可以看作是在此基础上多增加了一个 random 指针的变体：

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

从链表源码结构可以推断，链表的核心操作（创建、遍历、插入、删除）都依赖对 next 指针的读写；而本题的深拷贝正是把「按 next 复制」扩展到「同时按 random 复制」，难点在于 random 指向的节点位置不确定，无法像 next 那样边遍历边顺序建立。

3.2 哈希表：为什么它能让「任意引用」被快速解析

哈希表文档 给出了哈希表的精确定义：

哈希表（Hash Table），又称散列表，是一种能通过关键码（Key）直接访问数据的结构。哈希表利用「键 $key$」和「哈希函数 $Hash(key)$」将关键码映射到表中的某个位置，从而实现高效的查找和存储。

本题中哈希表扮演的角色非常特殊：它的键不是普通的值，而是旧节点的对象引用（在 Python 中，对象默认按身份 id 计算哈希，且 Node 节点并未重写 __eq__/__hash__，因此每个旧节点都是独一无二的键）。通过 node_dict[curr] = new_node 登记映射后，后续只需要 node_dict[旧节点] 就能以平均 $O(1)$ 时间取出对应的新节点——这正是哈希表「通过键直接访问数据」能力的体现。

在仓库的 哈希表实现与练习 中，还可以进一步了解哈希函数的构造方法与哈希冲突的解决策略（开放地址法、链地址法），这些是理解哈希表为何能在平均 $O(1)$ 时间内完成查找的底层依据。

4. 边界情况与常见错误排查

4.1 边界情况

场景	处理方式
空链表 head = None	直接返回 None，代码开头的 if not head 已覆盖
单节点链表（random 指向自身或 null）	第一遍登记映射后，第二遍 node_dict[curr].random = node_dict[curr.random] 能正确指向自身对应的新节点
random 指向头节点	头节点在第一遍遍历时已登记，第二遍可通过 node_dict 命中
random 指向尾部节点	尾部节点同样在第一遍已被登记，不受「尚未创建」影响
random = null	第二遍的 if curr.random: 判断跳过，新节点 random 保持 None

4.2 常见错误

1. 先设置 next 再处理 random，导致 random 指向旧节点：node_dict[curr].random = curr.random 是典型错误写法，这会让新节点的 random 直接引用旧节点，属于浅拷贝。正确写法是 node_dict[curr].random = node_dict[curr.random]，通过哈希表映射到新节点。
2. 忘记对 curr.random 判空：如果 random 为 null，直接写 node_dict[curr.random] 会抛出 KeyError（因为 node_dict 中不存在 None 这个键）。代码中的 if curr.random: 就是为了规避这一点。
3. 第一遍遍历时急于设置 next：如果边创建节点边设置 next，会形成「新节点链」，但此时 random 目标未必已创建，仍需第二遍补全；而「先全部创建、再统一连线」的两遍法可以同时覆盖 next 与 random，逻辑更简洁统一。
4. 返回了旧链表的头节点：深拷贝要求返回新建链表的头节点，即 node_dict[head]，而不是 head 本身。

5. 方法拓展与对比

5.1 思路 2：原地复制（O(1) 额外空间）

如果面试中被要求空间复杂度优化到 $O(1)$，可以使用「原地复制」思路：

1. 复制节点：遍历原链表，在每个旧节点 A 之后插入一个值相同的新节点 A'，即 A -> A' -> B -> B' -> ...。
2. 设置 random：再次遍历，让每个新节点 A'.random 指向 A.random 的复制节点（即 A.random.next，若 A.random 为 null 则保持 null）。
3. 拆分链表：第三次遍历，把奇数位置的旧节点串回原链表，把偶数位置的新节点拆出来组成新链表。

该思路的时间复杂度仍为 $O(n)$，但空间复杂度降为 $O(1)$（不借助哈希表，仅使用指针变量）。相比哈希表方案，代码略繁琐，但省去了 $O(n)$ 的映射空间，是进阶面试中常见的追问点。

5.2 思路 3：递归 + 哈希表

也可以把「旧节点 → 新节点」的映射放到递归中维护：

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        cache = {}

        def dfs(node):
            if not node:
                return None
            if node in cache:
                return cache[node]
            new_node = Node(node.val, None, None)
            cache[node] = new_node
            new_node.next = dfs(node.next)
            new_node.random = dfs(node.random)
            return new_node

        return dfs(head)

递归写法借助 cache 记录已创建的克隆节点，遇到环或重复引用时直接返回缓存结果，天然防止死循环。需要注意：Python 默认递归深度限制（约 1000）与题目数据范围 $n \le 1000$ 接近，极端情况下可能触发 RecursionError，因此迭代写法在工程上更稳妥。

5.3 两种主流思路对比

方法	时间复杂度	空间复杂度	代码复杂度	适用场景
哈希表 + 两遍遍历	$O(n)$	$O(n)$	低，逻辑清晰	面试首选，便于讲解与实现
原地复制 + 三次遍历	$O(n)$	$O(1)$	中，需注意指针拆分的边界	要求 $O(1)$ 空间的进阶追问
递归 + 哈希表	$O(n)$	$O(n)$（含递归栈）	低	习惯递归写法时可选，注意递归深度

6. 触类旁通：同思路题目串讲

「先通过哈希表建立旧结构到新结构的映射，再统一补齐指针关系」这一思路，在本仓库题解库中还有多个姊妹题，强烈建议对照阅读：

• 0133. 克隆图：以邻接表形式给定无向图，返回图的深拷贝。其哈希表思路与本题完全同构——visited 以「原图节点：克隆节点」为映射，配合 DFS/BFS 遍历原图，克隆节点时若已在映射表中则直接复用，防止重复创建。两者共同印证了「哈希表映射是深拷贝类问题的通用骨架」。
• 0146. LRU 缓存：LRU 缓存的实现同样需要「哈希表 + 双向链表」的组合，哈希表提供 $O(1)$ 的键值定位，链表维护访问顺序，可进一步体会两类数据结构协同工作的模式。

此外，本题所在的 0100-0199 题解索引 中还收录了大量链表与哈希表题目，例如 0141. 环形链表、0142. 环形链表 II、0143. 重排链表、0146. LRU 缓存，以及哈希表专题的 0706. 设计哈希映射 等，可以按需展开系统训练。

7. 总结

本题「随机链表的复制」是哈希表 + 链表的经典面试题，考察的核心能力有三层：

1. 深拷贝的概念理解：新链表的所有节点必须全部新建，新旧链表互不影响，任何「直接复用旧节点引用」的做法都是浅拷贝。
2. 哈希表映射的设计：以「旧节点：新节点」为键值对，先完成全部节点创建，再统一补齐 next 与 random 指针，从而化解 random 指向任意位置带来的「目标节点未创建」难题。
3. 复杂度与边界的把握：$O(n)$ 时间、$O(n)$ 空间的两遍遍历方案清晰可靠；在此基础上，还可向 $O(1)$ 空间的原地复制方案延伸，体现对链表指针操作的熟练度。

对照仓库 链表基础文档、链表源码实现、哈希表文档 与 克隆图题解 系统复习，即可把这一道题吃透，并顺带掌握一类「映射 + 复制」问题的通用解法。