deep copy: copy fields which are not reference of an object, which means objects need to be reconstructed and then be saved to the corresponding field of the target field which stores object reference.
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
# time O(2N) space O(1)
def copyRandomList(self, head: 'Node') -> 'Node':
p1 = p2 = head
d = dict()
d[None] = None
# step1, save all nodes in a dictionary as keys and refer to a new node with only node.val
while p1:
d[p1] = Node(p1.val) # create a new node
p1 = p1.next
# step2: for each node, based on original node's reference(next and random) to generate new Node and connect with nodes that generated in step 1
while p2:
d[p2].next = d.get(p2.next)
d[p2].random = d.get(p2.random)
p2 = p2.next
return d.get(head)
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
# main idea: initialize Node when it's stored in the dictionary
# time O(N) space O(1)
def copyRandomList(self, head: 'Node') -> 'Node':
d = collections.defaultdict(lambda:Node(-1))
d[None] = None
node = head
while node:
d[node].val = node.val # create a new node
d[node].next = d[node.next]
d[node].random = d[node.random]
node = node.next
return d[head]