时间复杂度为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)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
