138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/description/
Difficulty: Medium
Topic: Hash Table, Linked List
Solution 0: Recursion
O(N) time, O(N) space
"""
# 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:
def __init__(self) -> None:
# key: original node visited, value: corresponding cloned node
self.cloned_dict = {}
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# Solution 0: Recursion
# Base Case
if head == None:
return None
# Base Case: already cloned
if head in self.cloned_dict:
return self.cloned_dict[head]
# Copy current head node
node = Node(head.val, None, None)
self.cloned_dict[head] = node
# Recursively clone next and random pointer
node.next = self.copyRandomList(head.next)
node.random = self.copyRandomList(head.random)
return node
Solution 1: Iteration
time, space.
"""
# 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:
def __init__(self) -> None:
# key: original node visited, value: corresponding cloned node
self.cloned_dict = {}
def get_cloned_node(self, node: 'Optional[Node]') -> 'Optional[Node]':
if node:
if node in self.cloned_dict:
return self.cloned_dict[node]
else:
self.cloned_dict[node] = Node(node.val, None, None)
return self.cloned_dict[node]
return None
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# Solution 1: Iteration
if head is None:
return None
old_node = head
new_node = Node(old_node.val, None, None)
self.cloned_dict[old_node] = new_node
while old_node:
new_node.random = self.get_cloned_node(old_node.random)
new_node.next = self.get_cloned_node(old_node.next)
old_node = old_node.next
new_node = new_node.next
return self.cloned_dict[head]