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:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
allnodes = {}
newhead = make_copy(head, allnodes)
return newhead
```