本文主要是介绍【leetcode--138随机链表的复制】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
疑问：为什么不能写成dic[cur] = cur.val，若这样实际上将cur.val赋值给了dic的键cur，而不是将一个新的Node（cur.val）对象赋给dic的键cur。这就意味着若cur.val的值一旦改变，字典dic中的值也会发生改变，因为是一个对象的引用。
实现哈希表可以有以下两种方式：
- 数组 + 链表
- 数组 + 二叉树
所以，哈希表本质上就是一个数组。只不过数组存放的是单一的数据，而哈希表中存放的是键值对。
"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head:returndic = {}cur = headwhile cur:dic[cur] = Node(cur.val)cur = cur.nextcur = headwhile cur:dic[cur].next = dic.get(cur.next)dic[cur].random = dic.get(cur.random)cur = cur.nextreturn dic[head]第一个while循环作用：遍历原链表，将原链表中的每个节点cur复制为一个新节点，并将这个新节点存储到字典dic中。
第二个while循环作用：处理复制链表中的next和random指针，在原链表中，每个节点的next和random指针可能指向其他节点，需要在复制链表中正确指向对应的新节点。
使用dic.get(cur.random)是为了处理可能存在空指针的情况。若原指针指向的是空，则返回None，就避免了直接使用dic.get(cur.random)可能导致的keyerror错误。
这篇关于【leetcode--138随机链表的复制】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
