# My short python solution with O(n) space complexity, could I do better?

• This solution makes a map between new members of the node class and existing members so the space complexity is O(n), although AFAIK, that's unavoidable since a deep copy must replicated the objects in the first palace. As best as I can tell, the solution is O(n) time.

If anybody can elaborate on space complexity that would be really helpful, I know that I am probably not seeing something important here.

``````def make_copy(node, tracker):
# Base cases: None or existing nodes are returned w/o recursion
if node is None:
return None
elif node in tracker:
return tracker[node]
# Make new node instance and map it to the old node
newnode = RandomListNode(node.label)
tracker[node] = newnode
# recursively copy the next and random pointers before return
newnode.next = make_copy(node.next, tracker)
newnode.random = make_copy(node.random, tracker)
return newnode

class Solution:
# @return a RandomListNode
allnodes = {}

• your code are so short. It's easy to understand . below is my code. It's too much line code than you.
but I think there is no need so much recursion call.

``````class Solution:
# @return a RandomListNode
def __init__(self):
self.nodeMap = {}
nodeMap = self.nodeMap
randomList = []
return None

nPrev = None
while temp != None:
node = RandomListNode(temp.label)
if temp not in nodeMap:
nodeMap[temp] = node
else:
break
if temp.random != None:
if temp.random not in nodeMap:
randomList.append((node,temp))
else:
node.random = nodeMap[temp.random]

nPrev = node
else:
nPrev.next = node
nPrev = nPrev.next
temp = temp.next
while randomList != []:
node, srcNode = randomList.pop()
if srcNode.random not in nodeMap:
node.random = self.copyRandomList(srcNode.random)
else:
node.random = nodeMap[srcNode.random]

• I made almost the same solution, but it failed to pass one very long input.
So I just copy your code, it meets the same problem.

``````class Solution:
# @return a RandomListNode
def __init__(self):
self.all = {}

return

else: