题目大意
#
给定一个链表的头节点 head，链表中每个节点除了 next 指针之外，还包含一个随机指针 random，该指针可以指向链表中的任何节点或者空节点。
要求：将该链表进行深拷贝。
解题思路
#
遍历链表，利用哈希表，以 旧节点: 新节点 为映射关系，将节点关系存储下来。
再次遍历链表，将新链表的 next 和 random 指针设置好。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
node_dict = dict()
curr = head
while curr:
new_node = Node(curr.val, None, None)
node_dict[curr] = new_node
curr = curr.next
curr = head
while curr:
if curr.next:
node_dict[curr].next = node_dict[curr.next]
if curr.random:
node_dict[curr].random = node_dict[curr.random]
curr = curr.next
return node_dict[head]
|