The first question to ask is : what will it actually is when a linked-list is with random pointer? The answer is a graph! So just follow the way one uses to deal with a graph, i.e. DFS or BFS whatever you like.

**DFS**

```
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
# Use DFS at first
self.visited = collections.defaultdict(RandomListNode)
return self.DFS(head)
def DFS(self, head):
if not head:
return None
if head not in self.visited:
newHead = RandomListNode(head.label) # newHead
self.visited[head] = newHead
newHead.next = self.DFS(head.next) # visit next branch
newHead.random = self.DFS(head.random) # visite random branch
return newHead
else:
return self.visited[head] # o/w return the refered as newHead
```

**BFS**

```
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
# Try BFS this time
# assume all node in queue have been copied before putting into the queue
if not head: return None
newHead = RandomListNode(head.label)
visited = {head:newHead}
queue = collections.deque([head])
nextQ = collections.deque([])
while queue:
node = queue.popleft()
newNode = visited[node] # creat new Node
# next branch
if node.next and node.next not in visited:
newNext = RandomListNode(node.next.label)
visited[node.next] = newNext
newNode.next = newNext
nextQ.append(node.next)
elif node.next: # check not None
newNode.next = visited[node.next] # connect copy
# random branch
if node.random and node.random not in visited:
newRan = RandomListNode(node.random.label)
visited[node.random] = newRan
newNode.random = newRan
nextQ.append(node.random)
elif node.random: # check not None
newNode.random = visited[node.random]
if not queue:
queue, nextQ = nextQ, queue # swap
return newHead
```