企业官网建设流程全解析

盐城网站建设找哪家好,wordpress邮件问题,建设旅游网站,seo推广软件排行榜前十名给你一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random #xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成#xff0c;其中每个新节点的值都设为其对应的原节点的值。新节点的 n…给你一个长度为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或指向链表中的节点。解题思路建立原节点与新节点的映射遍历原链表为每个原节点创建对应的新节点仅复制val用哈希表存储 “原节点→新节点” 的对应关系填充新节点的next和random再次遍历原链表通过哈希表找到新节点对应的next原节点next对应的新节点和random原节点random对应的新节点返回新链表头节点从哈希表中取出原链表头节点对应的新节点作为复制链表的头节点。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) # 仅初始化valnext/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指向的valNone则标为Null random_val current.random.val if current.random else Null result.append(fVal: {current.val}, Random: {random_val}) current current.next print( - .join(result)) if __name__ __main__: # 构造测试链表1 - 2 - 3 # random指向1→32→13→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)。