LogicStack-LeetCode 题解精读：LeetCode 138「复制带随机指针的链表」——哈希表映射与原地 O(1) 空间两种深拷贝方案

本篇文章基于开源仓库「宫水三叶的刷题日记」刷穿 LeetCode 系列中的 LeetCode 138. 复制带随机指针的链表（中等）题解 展开精读。文章将完整还原题目要求与两种经典解法（「模拟 + 哈希表」与「原地 O(1) 空间算法」）的 Java / C++ / Python 三语言实现，并结合仓库中的 链表专题索引、哈希表专题索引 以及同源题目 剑指 Offer 35. 复杂链表的复制 做纵深对照。读完本文，你将掌握深拷贝含 random 随机指针链表的完整思考路径、两种解法的取舍依据与可直接提交的代码模板。

题目理解：什么是「带随机指针的链表」深拷贝

问题描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。要求构造这个链表的深拷贝。

深拷贝的定义非常严格，需要同时满足以下三条：

1. 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值；
2. 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态；
3. 复制链表中的指针都不应指向原链表中的节点。

用一句更直白的话说：例如原链表中有 X 和 Y 两个节点，其中 X.random --> Y；那么在复制链表中对应的两个节点 x 和 y，同样必须有 x.random --> y，且 x、y 必须是全新分配的节点。

输入 / 输出格式

题目用一个由 n 个节点组成的链表来表示输入/输出中的链表，每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数；
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null。

你的代码只接受原链表的头节点 head 作为传入参数，返回复制链表的头节点。

示例与约束

示例 1

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

示例 2

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

示例 3

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4

输入：head = []
输出：[]

解释：给定的链表为空（空指针），因此返回 null。

提示（约束条件）

• 0 <= n <= 1000
• -10000 <= Node.val <= 10000

本题在仓库 链表专题索引 与 哈希表专题索引 中均有收录，标签为「哈希表」「链表」，难度为中等。

解法一：模拟 + 哈希表（O(n) 空间）

思路拆解

如果不考虑 random 指针，对一条链表进行拷贝，只需要使用两个指针：一个用于遍历原链表，一个用于构造新链表（始终指向新链表的尾部）即可。这一步操作可以看作是「创建节点 + 构建 next 指针关系」。

现在在此基础上增加一个 random 指针，核心难点在于：random 可能指向链表中任意位置的节点，复制时如何快速知道「原节点对应的新节点是谁」？

解法一的做法是：把 next 指针和 random 指针关系的构建拆开进行，分两步：

1. 先不考虑 random 指针，和原本的链表复制一样，创建新节点并构造 next 指针关系，同时使用「哈希表」记录原节点 → 新节点的映射关系；
2. 对原链表和新链表进行同时遍历，对于原链表的每个节点上的 random，都通过「哈希表」找到对应的新 random 节点，并在新链表上构造 random 关系。

因为哈希表中存的是「原节点 → 新节点」的完整映射，所以无论 random 指向前面的节点、后面的节点还是 null，都能在 O(1) 时间内完成转换。

Java 实现

class Solution {
    public Node copyRandomList(Node head) {
        Node t = head;
        Node dummy = new Node(-10010), cur = dummy;
        Map<Node, Node> map = new HashMap<>();
        while (head != null) {
            Node node = new Node(head.val);
            map.put(head, node);
            cur.next = node;
            cur = cur.next; head = head.next;
        }
        cur = dummy.next; head = t;
        while (head != null) {
            cur.random = map.get(head.random);
            cur = cur.next; head = head.next;
        }
        return dummy.next;
    }
}

C++ 实现

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* t = head;
        unordered_map<Node*, Node*> map;
        Node* dummy = new Node(-1);
        Node* cur = dummy;
        while (head) {
            Node* node = new Node(head->val);
            map[head] = node;
            cur->next = node;
            cur = cur->next; head = head->next;
        }
        cur = dummy->next; head = t;
        while (head) {
            cur->random = map[head->random];
            cur = cur->next; head = head->next;
        }
        return dummy->next;
    }
};

Python 实现

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        mapping = {}
        dummy = Node(-1, None, None)
        cur = dummy
        t = head

        while head:
            node = Node(head.val, None, None)
            mapping[head] = node
            cur.next = node
            cur = cur.next
            head = head.next

        cur = dummy.next
        head = t
        while head:
            cur.random = mapping.get(head.random, None)
            cur = cur.next
            head = head.next

        return dummy.next

复杂度分析

• 时间复杂度：$O(n)$，两个线性遍历，每个节点均摊常数次操作；
• 空间复杂度：$O(n)$，额外使用了一个哈希表记录全部 n 个节点的映射关系。

解法二：模拟（原地算法，O(1) 空间）

思路拆解：为什么还能优化？

显然时间复杂度上已经无法优化（任何深拷贝都必须遍历全部节点），因此考虑如何降低空间（不使用「哈希表」）。

我们使用「哈希表」的目的是实现原节点和新节点的映射关系，更进一步是为了快速找到某个节点 random 在新链表中的位置。那么能否利用原链表的 next 指针做一个临时中转，从而在不需要额外哈希表的情况下实现同样的映射？答案是可以的，具体按三步走：

1. 复制节点并追加到原节点之后：对原链表的每个节点进行复制，将新节点插入到原节点与它的下一个节点之间；
2. 构造新节点的 random 关系：完成第 1 步之后，链表奇数位置代表原链表节点、偶数位置代表新链表节点，且每个原节点的 next 指向对应的新节点。此时利用公式 link[i + 1].random = link[i].random.next（i 为奇数下标）构造 random 关系，含义为：新链表节点的 random 指针，指向旧链表对应节点的 random 指针的下一个值；
3. 拆分链表：将交错在一起的链表拆回「原链表」和「新链表」两条独立链表，返回新链表头节点。

这一步的关键巧妙之处在于：新节点紧跟在原节点之后，因此「原节点的 random 所指向的原节点」的 next 恰好就是「新节点对应的 random 目标」，完全不需要额外映射表。

Java 实现

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return head;
        Node t = head;
        while (head != null) {
            Node node = new Node(head.val);
            node.next = head.next;
            head.next = node;
            head = node.next;
        }
        head = t;
        while (head != null) {
            if (head.random != null) head.next.random = head.random.next;
            head = head.next.next;
        }
        head = t;
        Node ans = head.next;
        while (head != null) {
            Node ne = head.next;
            if (ne != null) head.next = ne.next;
            head = ne;
        }
        return ans;
    }
}

C++ 实现

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node* t = head;
        while (head) {
            Node* node = new Node(head->val);
            node->next = head->next;
            head->next = node;
            head = node->next;
        }
        head = t;
        while (head) {
            if (head->random)  head->next->random = head->random->next;
            head = head->next->next;
        }
        head = t;
        Node* ans = head->next;
        while (head) {
            Node* ne = head->next;
            if (ne) head->next = ne->next;
            head = ne;
        }
        return ans;
    }
};

Python 实现

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        t = head

        while head:
            node = Node(head.val)
            node.next = head.next
            head.next = node
            head = node.next

        head = t
        while head:
            if head.random:
                head.next.random = head.random.next
            head = head.next.next

        head = t
        ans = head.next
        while head:
            ne = head.next
            head.next = ne.next if ne else None
            head = ne
        return ans

复杂度分析

• 时间复杂度：$O(n)$，共三轮线性遍历（复制插入、构造 random、拆分链表）；
• 空间复杂度：$O(1)$，除返回的新链表本身占用的 n 个新节点外，仅使用常数个指针变量。

两种解法对比与边界情况

对比维度	解法一：模拟 + 哈希表	解法二：原地算法
核心思想	用哈希表建立「原节点 → 新节点」映射	利用原链表的 next 作为临时中转实现映射
时间复杂度	$O(n)$	$O(n)$
空间复杂度	$O(n)$（哈希表）	$O(1)$（仅指针变量）
实现难度	较低，思路直观	略高，需要对交错链表结构有清晰认知
边界情况	需额外处理 random == null（哈希表 get 返回 null）	需额外处理 head == null 与 random == null

几个值得注意的边界细节：

• 空链表：解法二在开头有 if (head == null) return head; 的判空保护，否则后续 head.next 访问会空指针异常；解法一遍历循环天然兼容空链表，返回 dummy.next 即为 null。
• random == null：解法二中必须用 if (head.random != null) 判断后再访问 head.random.next，否则对 null 取 next 会触发异常；解法一中哈希表 get(null) 直接返回 null，天然安全。
• Node.val 的取值范围为 [-10000, 10000]：解法一 Java 代码中 dummy 哨兵节点取值 -10010，刻意低于取值范围下限，仅为占位使用，不会与真实节点值混淆。
• 拆分链表时：head = ne 的推进方式保证了每轮循环中 head 依次指向「原节点 → 新节点 → 原节点 → 新节点……」，从而正确地把交错链表分离为两条独立链表；Python 版本在 ne 为 None（遍历到原链表最后一个新节点）时需显式置 head.next = None，避免残留指针。

仓库同源对照：剑指 Offer 35「复杂链表的复制」

值得说明的是，本题并非孤立存在。在仓库的 剑指 Offer 目录 中，剑指 Offer 35. 复杂链表的复制（中等）.md 与 LeetCode 138 是完全同源的题目：题目描述、示例、约束与两种解法的思路几乎一致，仅 LeetCode 138 的 Python 签名使用 Optional[Node] 类型标注，而剑指 Offer 35 使用 'Node'。

从源码结构看，两篇题解采用了相同的「一题双解」框架：

• 「模拟 + 哈希表」两篇均给出 Java / C++ / Python 三语言完整实现；
• 「模拟（原地算法）」两篇的代码结构逐行对应，仅哨兵节点取值（LeetCode 138 为 -10010，剑指 Offer 35 在 C++/Python 中略有差异）与类型标注不同。

这组对照提示我们：同一道算法题在 LeetCode 与剑指 Offer 两个题集里反复出现，是高频面试考点；掌握「哈希表映射」与「原地拆分」两种范式后，可以一套思路通吃两处题源。

专题索引与延伸阅读

在仓库中，本题同时被归类到两个专题索引之下，读者可以根据自己的复习路线继续深入：

• Index/链表.md：链表专题索引，收录了本题及 2. 两数相加、141. 环形链表、146. LRU 缓存机制 等链表经典题，推荐指数为 🤩🤩🤩；
• Index/哈希表.md：哈希表专题索引，本题被收录其中，同目录下还有 380. O(1) 时间插入、删除和获取随机元素%20时间插入、删除和获取随机元素（中等）.md) 等利用哈希表维护映射关系的题目。

此外，README.md 说明了仓库的定位——「日更」算法题解仓库，按 Tag 分类组织内容；本系列文章在讲解解题思路之外，还会给出尽可能简洁的代码，涉及通解时附带代码模板，方便读者在本地调试与提交。

小结

LeetCode 138「复制带随机指针的链表」是一道考察「深拷贝」本质与「映射关系」构建能力的经典中等题。两条解题主线值得反复体会：

1. 哈希表方案（O(n) 空间）：把「节点间关系复制」拆成 next 与 random 两步，用映射表弥合新旧链表之间的引用鸿沟，直观、易写、不易错；
2. 原地方案（O(1) 空间）：利用原链表 next 做临时中转，将新节点插在原节点之后，再用「新节点 random = 原节点 random 的 next」完成关系重建，最后拆分链表，是面试中展示空间优化能力的加分项。

结合仓库中 链表专题索引、哈希表专题索引 以及 剑指 Offer 35 的同源对照，建议读者把两种实现都手写一遍，并重点练习 random == null 与空链表两类边界用例，即可在面试与笔试中从容应对这道高频题。