# Simple clean O(n) Python solution beats 81%

• 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):
"""
:rtype: RandomListNode
"""
return

currNode = RandomListNode(0)
visitD = {}
return currNode

nextN = RandomListNode(0)
currNode.next = nextN
else: