# Simple Python solution, beats 95%, O(n) time

• ``````def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if head == None:
return None
if head.next == None:
newHead = RandomListNode(head.label)
if head.random != None:
newHead.random = newHead
return newHead

nodeDict = self.buildNodeDict(head)
newNodeDict = dict()
newHead = RandomListNode(head.label)

# constract the normal list structure, consider the random pointers later.
# firstly, build a new dict for the copy of random list, get a copy of
# each node in the original list
p = head
while p != None:
newNodeDict[nodeDict[p]] = RandomListNode(p.label)
p = p.next
# link the list
for k, v in newNodeDict.items():
if k != len(nodeDict)-1:
v.next = newNodeDict[k+1]
# now consider the random pointers
p = head
while p != None:
if p.random != None:
newNodeDict[nodeDict[p]].random = newNodeDict[nodeDict[p.random]]
p = p.next

return newNodeDict[0]

def buildNodeDict(self, head):
nodeDict = dict()
i = 0
while head != None:
nodeDict[head] = i
head = head.next
i += 1

return nodeDict``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.