Copy Linked List with Random Pointer
Problem Statement
You are given the head of a linked list of length n
. Unlike a singly linked list, each node contains an additional pointer random
, which may point to any node in the list, or null
.
Create a deep copy of the list.
The deep copy should consist of exactly n
new nodes, each including:
- The original value
val
of the copied node - A
next
pointer to the new node corresponding to thenext
pointer of the original node - A
random
pointer to the new node corresponding to therandom
pointer of the original node
Note: None of the pointers in the new list should point to nodes in the original list.
Return the head of the copied linked list.
In the examples, the linked list is represented as a list of n
nodes. Each node is represented as a pair of [val, random_index]
where random_index
is the index of the node (0-indexed) that the random
pointer points to, or null
if it does not point to any node.
Example 1:
Input: head = [[3,null],[7,3],[4,0],[5,1]]
Output: [[3,null],[7,3],[4,0],[5,1]]
Example 2:
Input: head = [[1,null],[2,2],[3,2]]
Output: [[1,null],[2,2],[3,2]]
You should aim for a solution as good or better than O(n)
time and O(n)
space, where n
is the length of the given list.
Recommended Time and Space Complexity
You should aim for a solution as good or better than O(n)
time and O(n)
space, where n
is the length of the given list.
Hint 1
There is an extra random pointer for each node, and unlike the next pointer, which points to the next node, the random pointer can point to any random node in the list. A deep copy is meant to create completely separate nodes occupying different memory. Why can’t we build a new list while iterating through the original list?
Hint 2
Because, while iterating through the list, when we encounter a node and create a copy of it, we can’t immediately assign the random pointer’s address. This is because the random pointer might point to a node that has not yet been created. To solve this, we can first create copies of all the nodes in one iteration. However, we still can’t directly assign the random pointers since we don’t have the addresses of the copies of those random pointers. Can you think of a data structure to store this information? Maybe a hash data structure could help.
Hint 3
We can use a hash data structure, such as a hash map, which takes O(1)
time to retrieve data. This can help by mapping the original nodes to their corresponding copies. This way, we can easily retrieve the copy of any node and assign the random pointers in a subsequent pass after creating copies of all nodes in the first pass.
Solution
Hash Map (Recursion)
"""# 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"""
def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]': node_map = {}
def deep_copy(node): if node is None: return None if node in node_map: return node_map[node]
copy = Node(node.val) node_map[node] = copy copy.next = deep_copy(node.next) copy.random = node_map.get(node.random) return copy
return deep_copy(head)
Time complexity: O(n)
Space complexity: O(n)
Hash Map (Two Pass)
"""# 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"""
def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]': old_to_copy = {None: None}
curr = head while curr: copy = Node(curr.val) old_to_copy[curr] = copy curr = curr.next curr = head while curr: copy = old_to_copy[curr] copy.next = old_to_copy[curr.next] copy.random = old_to_copy[curr.random] curr = curr.next return old_to_copy[head]
Time complexity: O(n)
Space complexity: O(n)
Hash Map (One Pass)
"""# 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"""
import collections
def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]': old_to_copy = collections.defaultdict(lambda: Node(0)) old_to_copy[None] = None
curr = head while curr: old_to_copy[curr].val = curr.val old_to_copy[curr].next = old_to_copy[curr.next] old_to_copy[curr].random = old_to_copy[curr.random] curr = curr.next return old_to_copy[head]
Time complexity: O(n)
Space complexity: O(n)
Space Optimized - I
"""# 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"""
def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]': if head is None: return None
l1 = head while l1 is not None: l2 = Node(l1.val) l2.next = l1.next l1.next = l2 l1 = l2.next
new_head = head.next
l1 = head while l1 is not None: if l1.random is not None: l1.next.random = l1.random.next l1 = l1.next.next
l1 = head while l1 is not None: l2 = l1.next l1.next = l2.next if l2.next is not None: l2.next = l2.next.next l1 = l1.next
return new_head
Time complexity: O(n)
Space complexity: O(1)
Space Optimized - II
"""# 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"""
def copy_random_list(head: 'Optional[Node]') -> 'Optional[Node]': if head is None: return None
l1 = head while l1: l2 = Node(l1.val) l2.next = l1.random l1.random = l2 l1 = l1.next
new_head = head.random
l1 = head while l1: l2 = l1.random l2.random = l2.next.random if l2.next else None l1 = l1.next
l1 = head while l1 is not None: l2 = l1.random l1.random = l2.next l2.next = l1.next.random if l1.next else None l1 = l1.next
return new_head
Time complexity: O(n)
Space complexity: O(1)