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 the next pointer of the original node
  • A random pointer to the new node corresponding to the random 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.

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)