时间复杂度为O(n)，需要额外空间O(n)
class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
d = dict()
pHead_new = self.digui(d, pHead)
temp = pHead
temp_new = pHead_new
while temp:
if temp.random:
temp_new.random = d[temp.random]
temp = temp.next
temp_new = temp_new.next
return pHead_new
def digui(self, d, node):
if not node:
return None
new_node = RandomListNode(node.label)
d[node] = new_node
new_node.next = self.digui(d, node.next)
return new_node
时间复杂度O(n)，无额外空间
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
self.digui(pHead)
temp = pHead
while temp:
if temp.random:
temp.next.random = temp.random.next
temp = temp.next.next
if pHead:
temp = pHead
pHead_new = pHead.next
while temp:
temp_1 = temp.next
if temp.next:
temp.next = temp.next.next
temp = temp_1
return pHead_new
else:
return None
def digui(self, node):
if node:
new_node = RandomListNode(node.label)
new_node.next = node.next
node.next = new_node
self.digui(new_node.next)
