My general approach is to understand this as a tree and do **in oder tree traversal**. That is head -> next -> random.

Initially, I pass in a created new node with value zero as **current node.**

When processing head of the old linkedlist, assign its value to the **current node**.

Add the id of head to a dictionary as key and value as the **current node** object.

If head.next exist, and head.next id is not in the dictionary, create new node with value zero and assign it as the next of the **current node**. Then do recursion with head next, current node next.

If head.next exist, and head.next id is in the dictionary, we just set the current node next to the value of the corresponding key in dictionary.

Same as random.

Since its an in order traversal, we going through the list once with O(n). Space complexity O(n) as well.

```
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if head == None:
return
currNode = RandomListNode(0)
visitD = {}
self.copyRandomListUtil(head, currNode, visitD)
return currNode
def copyRandomListUtil(self, head, currNode, visitD):
currNode.label = head.label
visitD[id(head)] = currNode
if head.next !=None:
if id(head.next) not in visitD:
nextN = RandomListNode(0)
currNode.next = nextN
self.copyRandomListUtil(head.next, currNode.next, visitD)
else:
currNode.next = visitD[id(head.next)]
if head.random !=None:
if id(head.random) not in visitD:
randomN = RandomListNode(0)
currNode.random = randomN
self.copyRandomListUtil(head.random, currNode.random, visitD)
else:
currNode.random = visitD[id(head.random)]
return
```