企业官网建设流程全解析

LeetCode-Book：剑指 Offer 35 复杂链表的复制全解——哈希表与拼接+拆分的 C++/Java/Python 双方法实现

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

剑指 Offer 35「复杂链表的复制」要求在复制普通链表的基础上，额外复制每个节点新增的random随机指针，它可能指向链表中任意节点或null，核心难点在于「新节点如何指向新链表中对应的新节点」。本文基于 LeetCode-Book 仓库中 剑指 Offer 35. 复杂链表的复制 一节的完整内容，系统讲解哈希表法与「拼接 + 拆分」法的算法流程、复杂度与 C++/Java/Python 三语言参考代码，并结合仓库中可运行的测试用例验证结果，读完后你可以独立实现并解释两种方法的每一步指针操作。

一、题目背景：random 指针为什么让复制变难

普通链表只有next指针，复制时只需遍历一遍，每轮建立新节点并构建「前驱新节点 -> 当前新节点」的引用指向即可。本题的节点新增了random指针，指向链表中的任意节点或者null，这意味着在复制过程中，除了构建pre.next（前驱新节点指向当前新节点），还必须构建pre.random（前驱新节点指向它的随机对应的新节点）。

节点定义：普通链表 vs 复杂链表

仓库文档先给出普通链表的节点定义作对比，再给出本题的节点定义。两种定义分别用三种语言给出，这也是仓库中可运行代码里实际使用的节点结构。

普通链表节点（Python）：

# Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None): self.val = int(x) self.next = next

普通链表节点（Java）：

// Definition for a Node. class Node { int val; Node next; public Node(int val) { this.val = val; this.next = null; } }

普通链表节点（C++）：

// Definition for a Node. class Node { public: int val; Node* next; Node(int _val) { val = _val; next = NULL; } };

本题链表的节点定义（Python）：

# Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random

本题链表的节点定义（Java）：

// Definition for a Node. class Node { int val; Node next, random; public Node(int val) { this.val = val; this.next = null; this.random = null; } }

本题链表的节点定义（C++）：

// Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } };

朴素思路的「死结」：pre.random = '???'

如果照搬普通链表的复制流程，会遇到一个无法当场解决的引用：新链表当前节点的random所指向的节点可能尚未被创建（random可以指向前面的节点，也可以指向后面的节点），因此遍历到某节点时根本无法确定pre.random该指向谁。三种语言的朴素实现都卡在同一步：

class Solution: def copyRandomList(self, head: 'Node') -> 'Node': cur = head dum = pre = Node(0) while cur: node = Node(cur.val) # 复制节点 cur pre.next = node # 新链表的 前驱节点 -> 当前节点 # pre.random = '???' # 新链表的 「 前驱节点 -> 当前节点 」 无法确定 cur = cur.next # 遍历下一节点 pre = node # 保存当前新节点 return dum.next

class Solution { public Node copyRandomList(Node head) { Node cur = head; Node dum = new Node(0), pre = dum; while(cur != null) { Node node = new Node(cur.val); // 复制节点 cur pre.next = node; // 新链表的 前驱节点 -> 当前节点 // pre.random = "???"; // 新链表的 「 前驱节点 -> 当前节点 」 无法确定 cur = cur.next; // 遍历下一节点 pre = node; // 保存当前新节点 } return dum.next; } }

class Solution { public: Node* copyRandomList(Node* head) { Node* cur = head; Node* dum = new Node(0), *pre = dum; while(cur != nullptr) { Node* node = new Node(cur->val); // 复制节点 cur pre->next = node; // 新链表的 前驱节点 -> 当前节点 // pre->random = "???"; // 新链表的 「 前驱节点 -> 当前节点 」 无法确定 cur = cur->next; // 遍历下一节点 pre = node; // 保存当前新节点 } return dum->next; } };

针对这个死结，本文介绍两种思路：哈希表方法比较直观，用空间换时间，通过「原节点 -> 新节点」的映射表把指向问题转化为查表问题；拼接 + 拆分方法的空间复杂度更低，通过把新节点插到原节点后面，利用几何位置关系cur.random.next直接定位到新链表中对应的节点。

二、方法一：哈希表

算法思想

利用哈希表的查询特点，构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的next和random引用指向。映射关系建立后，「新链表中任意节点的 next / random」都可以通过一次查表（O(1)）得到，彻底解开了pre.random = '???'的死结。

算法流程

1. 若头节点head为空节点，直接返回null；
2. 初始化：哈希表dic，节点cur指向头节点；
3. 复制链表：
   1. 建立新节点，并向dic添加键值对(原 cur 节点, 新 cur 节点)；
   2. cur遍历至原链表下一节点；
4. 构建新链表的引用指向：
   1. 构建新节点的next和random引用指向；
   2. cur遍历至原链表下一节点；
5. 返回值：新链表的头节点dic[head]。

整个算法分为「先建映射，再连指针」两遍遍历：第一遍保证映射表完整覆盖所有节点，第二遍连指针时表查询才不会落空。

复杂度分析

• 时间复杂度 O(N)：两轮遍历链表，使用 O(N) 时间（哈希表单次插入/查询为 O(1)）。
• 空间复杂度 O(N)：哈希表dic使用线性大小的额外空间。

三语言参考代码

Python 实现，注意dic.get(cur.next)的妙处：当cur.next为None时，dict.get返回None，天然完成了空指针映射，不需要额外的判空语句。

class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return dic = {} # 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 cur = head while cur: dic[cur] = Node(cur.val) cur = cur.next cur = head # 4. 构建新节点的 next 和 random 指向 while cur: dic[cur].next = dic.get(cur.next) dic[cur].random = dic.get(cur.random) cur = cur.next # 5. 返回新链表的头节点 return dic[head]

Java 实现，map.get(cur.next)对不存在的键返回null，同样天然处理空指针：

class Solution { public Node copyRandomList(Node head) { if(head == null) return null; Node cur = head; Map<Node, Node> map = new HashMap<>(); // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 while(cur != null) { map.put(cur, new Node(cur.val)); cur = cur.next; } cur = head; // 4. 构建新链表的 next 和 random 指向 while(cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } // 5. 返回新链表的头节点 return map.get(head); } }

C++ 实现。从源码看，这里使用map[cur->next]而非map.find：std::unordered_map的operator[]对不存在的键会插入一个值为nullptr的默认条目，因此cur->next或cur->random为nullptr时表达式安全求值为nullptr，行为与两种脚本语言的get完全一致。

class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; unordered_map<Node*, Node*> map; // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 while(cur != nullptr) { map[cur] = new Node(cur->val); cur = cur->next; } cur = head; // 4. 构建新链表的 next 和 random 指向 while(cur != nullptr) { map[cur]->next = map[cur->next]; map[cur]->random = map[cur->random]; cur = cur->next; } // 5. 返回新链表的头节点 return map[head]; } };

仓库可运行源码

上述算法在仓库中的完整可运行版本（含节点定义与测试用例）见：

• Python：sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.py
• Java：sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.java
• C++：sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.cpp

三、方法二：拼接 + 拆分

算法思想

考虑构建原节点1 -> 新节点1 -> 原节点2 -> 新节点2 -> ……的拼接链表。这样每个新节点都紧挨在对应原节点的后面，当访问原节点cur的随机指向节点cur.random时，对应新节点cur.next的随机指向节点恰好是cur.random.next——新节点random指向节点在拼接链表中可以通过一次next跳转直接找到，无需任何映射表。

算法流程

1. 复制各节点，构建拼接链表：

   设原链表为node1 -> node2 -> ...，构建的拼接链表如下所示：

   node1 -> node1_new -> node2 -> node2_new -> ...

2. 构建新链表各节点的random指向：

   当访问原节点cur的随机指向节点cur.random时，对应新节点cur.next的随机指向节点为cur.random.next。

3. 拆分原 / 新链表：

   设置pre/cur分别指向原 / 新链表头节点，遍历执行pre.next = pre.next.next和cur.next = cur.next.next将两链表拆分开。

4. 返回新链表的头节点res即可。

复杂度分析

• 时间复杂度 O(N)：三轮遍历链表，使用 O(N) 时间。
• 空间复杂度 O(1)：节点引用变量使用常数大小的额外空间。

三语言参考代码

Python 实现。第一步的关键是三行指针重排：tmp.next = cur.next先保存原后继，cur.next = tmp再插入新节点，最后cur = tmp.next跳过新节点、回到原链表的下一节点，从而在拼接链表中以「原节点」的节奏推进。

class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return cur = head # 1. 复制各节点，并构建拼接链表 while cur: tmp = Node(cur.val) tmp.next = cur.next cur.next = tmp cur = tmp.next # 2. 构建各新节点的 random 指向 cur = head while cur: if cur.random: cur.next.random = cur.random.next cur = cur.next.next # 3. 拆分两链表 cur = res = head.next pre = head while cur.next: pre.next = pre.next.next cur.next = cur.next.next pre = pre.next cur = cur.next pre.next = None # 单独处理原链表尾节点 return res # 返回新链表头节点

Java 实现：

class Solution { public Node copyRandomList(Node head) { if(head == null) return null; Node cur = head; // 1. 复制各节点，并构建拼接链表 while(cur != null) { Node tmp = new Node(cur.val); tmp.next = cur.next; cur.next = tmp; cur = tmp.next; } // 2. 构建各新节点的 random 指向 cur = head; while(cur != null) { if(cur.random != null) cur.next.random = cur.random.next; cur = cur.next.next; } // 3. 拆分两链表 cur = head.next; Node pre = head, res = head.next; while(cur.next != null) { pre.next = pre.next.next; cur.next = cur.next.next; pre = pre.next; cur = cur.next; } pre.next = null; // 单独处理原链表尾节点 return res; // 返回新链表头节点 } }

C++ 实现：

class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; // 1. 复制各节点，并构建拼接链表 while(cur != nullptr) { Node* tmp = new Node(cur->val); tmp->next = cur->next; cur->next = tmp; cur = tmp->next; } // 2. 构建各新节点的 random 指向 cur = head; while(cur != nullptr) { if(cur->random != nullptr) cur->next->random = cur->random->next; cur = cur->next->next; } // 3. 拆分两链表 cur = head->next; Node* pre = head, *res = head->next; while(cur->next != nullptr) { pre->next = pre->next->next; cur->next = cur->next->next; pre = pre->next; cur = cur->next; } pre->next = nullptr; // 单独处理原链表尾节点 return res; // 返回新链表头节点 } };

仓库可运行源码

• Python：sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.py
• Java：sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.java
• C++：sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.cpp

方法二的三个实践要点

结合仓库源码可以确认三个容易出错的细节：

1. 拆分的 while 条件是cur.next而非cur：拆分循环处理到倒数第二个节点对时退出，原链表尾节点的next需要在循环外单独置空（pre.next = None），否则原链表会错误地挂上新链表的尾节点；
2. 第二步必须判空：cur.random为null时不能执行cur.random.next，三种语言实现都保留了if cur.random:的判断；
3. 拼接法是「原地修改」算法：第一步直接改写原链表的next指针。虽然算法在拆分结束后会完整恢复原链表的next结构，但它对原链表产生了副作用，这在多线程环境或要求输入只读的场景中需要特别注意——而方法一的哈希表法完全不触碰原链表，是更稳妥的选择。

四、测试用例与结果验证

仓库中三种语言、两种方法的可运行文件均内置了同一组 LeetCode 官方测试用例：节点值序列{7, 13, 11, 10, 1}，random 指向序列{null, 0, 4, 2, 0}（下标表示指向第几个节点，null表示指向空）。以 Python 方法一的测试代码 为例：

test_case = [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]] # Construct nodes node_list = [Node(val) for val, _ in test_case] # Build next reference for i in range(len(test_case) - 1): node_list[i].next = node_list[i + 1] # Build random reference for i in range(len(test_case)): if test_case[i][1] != None: node_list[i].random = node_list[test_case[i][1]]

驱动代码调用Solution().copyRandomList(head)后，会遍历新链表并打印每个新节点的[值, random 指向的新节点下标]，预期输出为：

[[7, None], [13, 0], [11, 4], [10, 2], [1, 0]]

C++ 版本由于没有null字面量，用INT_MAX表示「指向空」，测试构造逻辑等价，见 C++ 方法一源码的 main 函数。该用例同时覆盖了「random 指向前驱节点（下标 0）」「指向后继节点（下标 4）」「指向自身所在链表的中间节点」三种典型形态，是验证random映射正确性的最小完备用例集。

五、两种方法的对比与选型

从源码结构看，两个方法的三语言实现与 题解文档 中的算法流程逐行对应，可以直接复制到本地作为可运行的独立程序验证。选型建议：面试白板作答优先写哈希表法，思路清晰、不易写错；追问「能否把空间复杂度降到 O(1)」时再展开拼接 + 拆分法；工程代码中若对输入只读有要求，同样推荐哈希表法。

六、仓库资源索引

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book