```
class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
dic = dict()
m = n = head
while m:
dic[m] = RandomListNode(m.label)
m = m.next
while n:
dic[n].next = dic.get(n.next)
dic[n].random = dic.get(n.random)
n = n.next
return dic.get(head)
```

O(n)

```
class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
dic = collections.defaultdict(lambda: RandomListNode(0))
dic[None] = None
n = head
while n:
dic[n].label = n.label
dic[n].next = dic[n.next]
dic[n].random = dic[n.random]
n = n.next
return dic[head]
```