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.nextclass 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 ???的死结。算法流程若头节点head为空节点直接返回null初始化哈希表dic节点cur指向头节点复制链表建立新节点并向dic添加键值对(原 cur 节点, 新 cur 节点)cur遍历至原链表下一节点构建新链表的引用指向构建新节点的next和random引用指向cur遍历至原链表下一节点返回值新链表的头节点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; MapNode, 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.findstd::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_mapNode*, 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]; } };仓库可运行源码上述算法在仓库中的完整可运行版本含节点定义与测试用例见Pythonsfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.pyJavasfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.javaCsfo_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跳转直接找到无需任何映射表。算法流程复制各节点构建拼接链表设原链表为node1 - node2 - ...构建的拼接链表如下所示node1 - node1_new - node2 - node2_new - ...构建新链表各节点的random指向当访问原节点cur的随机指向节点cur.random时对应新节点cur.next的随机指向节点为cur.random.next。拆分原 / 新链表设置pre/cur分别指向原 / 新链表头节点遍历执行pre.next pre.next.next和cur.next cur.next.next将两链表拆分开。返回新链表的头节点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; // 返回新链表头节点 } };仓库可运行源码Pythonsfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.pyJavasfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.javaCsfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.cpp方法二的三个实践要点结合仓库源码可以确认三个容易出错的细节拆分的 while 条件是cur.next而非cur拆分循环处理到倒数第二个节点对时退出原链表尾节点的next需要在循环外单独置空pre.next None否则原链表会错误地挂上新链表的尾节点第二步必须判空cur.random为null时不能执行cur.random.next三种语言实现都保留了if cur.random:的判断拼接法是「原地修改」算法第一步直接改写原链表的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(N)两轮遍历O(N)三轮遍历空间复杂度O(N)映射表O(1)仅常数个指针变量对原链表的副作用无纯只读遍历有先插节点再拆回过程中临时破坏原next结构直观程度直观查表即得指向需要理解拼接链表中cur.random.next的几何关系工程适用性通用性最强可平移到任何带交叉引用的图复制问题仅限「单链表 局部跳转」结构从源码结构看两个方法的三语言实现与 题解文档 中的算法流程逐行对应可以直接复制到本地作为可运行的独立程序验证。选型建议面试白板作答优先写哈希表法思路清晰、不易写错追问「能否把空间复杂度降到 O(1)」时再展开拼接 拆分法工程代码中若对输入只读有要求同样推荐哈希表法。六、仓库资源索引资源相对路径题解文档本文主体来源sword_for_offer/docs/剑指 Offer 35. 复杂链表的复制.mdPython 方法一哈希表sword_for_offer/codes/python/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.pyPython 方法二拼接 拆分sword_for_offer/codes/python/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.pyJava 方法一sword_for_offer/codes/java/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.javaJava 方法二sword_for_offer/codes/java/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.javaC 方法一sword_for_offer/codes/cpp/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s1.cppC 方法二sword_for_offer/codes/cpp/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2/sfo_35_clone_a_linked_list_with_next_and_random_pointer_s2.cpp【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
