面试题面试题35. 复杂链表的复制复杂链表的复制
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
思路思路1：回溯：回溯
将链视作一个图
"""
# 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 __init__(self):
# 建立字典（哈希映射），将旧节点作为键，新节点作为值
self.visitedHash={}
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
# 如果已经复制过当前节点，那么只需返回它的复制版本
if head in self.visitedHash:
return self.visitedHash[head] # 如果没有复制国当前节点，那么创建一个和当前节点值相同的节点
node = Node(head.val, None, None)
# 将复制的节点加入到字典（哈希映射）中，这可以防止因为随机指针的随机性原因可能会出现的循环
self.visitedHash[head] = node
# 下一个指针开始，从随机指针开始，递归的复制余下的链表
node.next = self.copyRandomList(head.next)
node.random = self.copyRandomList(head.random)
return node
思路思路2：：O(N) 空间的迭代空间的迭代
迭代算法不需要将链表视为一个图。当在迭代链表时，只需为random指针和next指针指向的未访问过节点创造新的节点并赋值。
算法：
从head节点开始遍历链表。下图中，首先创建新的head拷贝节点。拷贝的节点如下图虚线所示。实现中，将新建节点的引用页放入已访问字典中。
random指针
*如果当前节点i的random指针指向一个节点j，且节点j已经被拷贝过，那么直接使用已访问字典中该节点的引用而不会新建节点。
*如果当前节点i的random指针指向一个节点j还没有被拷贝过，就到j节点创建对应的新节点，并把它放入已访问节点字典中
下图中， A 的 random 指针指向的节点 C 。前图中可以看出，节点 C 还没有被访问过，所以我们创造一个拷贝的 C’节点与之对应，并将它添加到已访问字典中。
资源评论
weixin_38654944
- 粉丝: 2
- 资源: 943
最新资源
- apache-maven-3.6.1-bin.zip
- c593f5fc-d4a7-4b43-8ab2-51afc90f3f62
- IIR滤波器参数计算函数
- WPF树菜单拖拽功能，下级目录拖到上级目录，上级目录拖到下级目录.zip
- CDH6.3.2版本hive2.1.1修复HIVE-14706后的jar包
- 鸿蒙项目实战-天气项目(当前城市天气、温度、湿度，24h天气，未来七天天气预报，生活指数，城市选择等)
- Linux环境下oracle数据库服务器配置中文最新版本
- Linux操作系统中Oracle11g数据库安装步骤详细图解中文最新版本
- SMA中心接触件插合力量（插入力及分离力）仿真
- 变色龙记事本，有NPP功能，JSONview功能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
