面试题面试题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
最新资源
- dbeaver-ce-24.3.1-x86-64-setup.exe
- 国际象棋桌子检测6-YOLO（v5至v9）、COCO、CreateML、Darknet、Paligemma、TFRecord数据集合集.rar
- 某平台广告投入分析与销售预测
- 连接ESP32手表来做验证20241223-140953.pcapng
- 小偏差线性化模型，航空发动机线性化，非线性系统线性化，求解线性系统具体参数，最小二乘拟合 MATLAB Simulink 航空发动机，非线性，线性，非线性系统，线性系统，最小二乘，拟合，小偏差，系统辨
- 好用的Linux终端管理工具，支持自定义多行脚本命令，密码保存、断链续接，SFTP等功能
- Qt源码ModbusTCP 主机客户端通信程序 基于QT5 QWidget, 实现ModbusTCP 主机客户端通信，支持以下功能： 1、支持断线重连 2、通过INI文件配置自定义服务器I
- QGroundControl-installer.exe
- 台球检测40-YOLO（v5至v11）、COCO、CreateML、Paligemma、TFRecord、VOC数据集合集.rar
- 颜色拾取器 for Windows
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
