【LeetCode刷题】随机链表的复制

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

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

例如，如果原链表中有X和Y两个节点，其中X.random --> Y。那么在复制链表中对应的两个节点x和y，同样有x.random --> 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]]

提示：

• 0 <= n <= 1000
• -104 <= Node.val <=
• Node.random为null或指向链表中的节点。

解题思路

1. 建立原节点与新节点的映射：遍历原链表，为每个原节点创建对应的新节点（仅复制val），用哈希表存储 “原节点→新节点” 的对应关系；
2. 填充新节点的next和random：再次遍历原链表，通过哈希表找到新节点对应的next（原节点next对应的新节点）和random（原节点random对应的新节点）；
3. 返回新链表头节点：从哈希表中取出原链表头节点对应的新节点，作为复制链表的头节点。

Python代码

# 导入必要的类型注解模块 from typing import Optional # 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 class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return None # 空链表直接返回 # 步骤1：建立原节点到新节点的映射（仅复制val） node_map = {} current = head while current: node_map[current] = Node(current.val) # 仅初始化val，next/random暂为None current = current.next # 步骤2：填充新节点的next和random指针 current = head while current: new_node = node_map[current] # 原节点的next/random可能为None，用get避免KeyError new_node.next = node_map.get(current.next) new_node.random = node_map.get(current.random) current = current.next # 步骤3：返回新链表的头节点 return node_map[head] # ====================== 测试用例 ====================== def print_linked_list(head: Node): """辅助函数：打印链表（val + random指向的val），验证复制结果""" current = head result = [] while current: # 记录当前节点val和random指向的val（None则标为Null） random_val = current.random.val if current.random else "Null" result.append(f"Val: {current.val}, Random: {random_val}") current = current.next print(" -> ".join(result)) if __name__ == "__main__": # 构造测试链表：1 -> 2 -> 3 # random指向：1→3，2→1，3→2 node1 = Node(1) node2 = Node(2) node3 = Node(3) node1.next = node2 node2.next = node3 node1.random = node3 node2.random = node1 node3.random = node2 print("原链表：") print_linked_list(node1) # 复制链表 solution = Solution() copied_head = solution.copyRandomList(node1) print("\n复制后的链表：") print_linked_list(copied_head) # 验证：复制后的链表与原链表内容一致，但内存地址不同（深拷贝） print(f"\n原链表头节点地址: {id(node1)}") print(f"复制链表头节点地址: {id(copied_head)}") print("复制结果验证：" + ("成功" if copied_head.val == 1 and copied_head.random.val == 3 else "失败"))

LeetCode提交代码

""" # 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 """ class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return None # 空链表直接返回 # 步骤1：建立原节点到新节点的映射 node_map = {} current = head while current: node_map[current] = Node(current.val) # 仅复制val current = current.next # 步骤2：填充新节点的next和random current = head while current: new_node = node_map[current] # next：原节点next对应的新节点（若原next为None则新next也为None） new_node.next = node_map.get(current.next) # random：原节点random对应的新节点（若原random为None则新random也为None） new_node.random = node_map.get(current.random) current = current.next # 步骤3：返回新链表的头节点 return node_map[head]

程序运行截图展示

总结

本文介绍了如何深拷贝带有随机指针的链表。通过两次遍历链表：第一次建立原节点到新节点的映射，第二次填充新节点的next和random指针。使用哈希表存储节点对应关系，确保新链表的指针指向正确的新节点而非原节点。Python实现包括节点类定义、深拷贝方法及测试用例，验证了复制链表与原链表结构一致但内存独立。该方法时间复杂度O(n)，空间复杂度O(n)。