Copy List with Random Pointer

The given Linked List

"""
# 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
"""

Given the Head of a Linked List, need to construct the deep copy of the given Linked List and return the Head of the new Linked List.

Unlike the usual Linked List Nodes, given Nodes will have Two pointers .next (which is obvious) and .random (might be new for us)
Now we need to construct the deep copy version of the given linked list. which will look like this bellow. Read the problem description for more details

Imagine that the Blue nodes are copied from the original nodes and Green arrows are links which are re-established among the copied nodes. We will solve this problem using Two Pass algorithm.
First pass:

Populate a HashMap where the copied nodes (value) mapped with the original nodes (key)

Second Pass:

Establish Links among the copied nodes

Pass 1: Copy Nodes and Map with Original Nodes

Iterate the given Linked List starting from the HEAD. Construct new instance of each nodes only with the values, and map the Copies with the Original nodes. This time we are not going establish the links among the nodes. So we are going to:

1. create the deep copy of original nodes only with the values | TC O(n)
2. save them into a HashMap | SC O(n)

Let's visualize the steps

The curr pointer is pointing at HEAD of the original Linked List which has value 7. We will create a new Node instance using the value of 7. Like this

copied_node = Node(curr.val)

In this pass, we will skip establishing .next and .random pointers. Let's map the new copied node with the original node in a HashMap/Dictionary as Key Value Pair where the original nodes will be the KEY and new copied nodes will be the VALUE

Here we can see in the HashMap, Node 7 got copied and mapped with the original node 7. Beside that, we also mapped NULL with NULL to avoid handling edge cases.

"""
# 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 copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
		# we will map the new nodes with original nodes here
		node_map = {None: None}  # init mapping with None value
		curr = head  # starting curr from head
		while curr:
			node_map[curr] = Node(curr.val)  # creating node instance, storing into HashMap
			curr = curr.next  # moving curr pointer forward

After finishing the loop, the output will look like this

Pass 2: Linking among the Copied Nodes

At this point, our node_map HashMap has all the mappings of Original to Copied nodes. It's time to establish .next and .random pointers among the copied nodes. Here are the TODOs

1. Set the curr pointer at the HEAD of the original linked list and iterate once again.
2. Lookup the Current Original Node in the HashMap to retrieve the Copied Node.
3. Then Retrieve copy of the curr.next node from HashMap.
4. Also Retrieve the copy of the curr.random node from HashMap.
5. Finally assign .next and .random pointer to the copied node we got at step 2

The curr pointer is pointing at Node 7. Lookup the Copied Node of Node 7 from HashMap. Then, Similarly retrieve the copy of .next and .random pointers.

Now we have the copy of current node and also the copy of .next and .random but they are not linked. Let's connect them.

We need to Keep Doing this process until the curr pointer at the End of the original Linked List.

curr = head
while curr:
	copied_curr = node_map[curr]  # lookup copied node from hashmap
	copied_curr_next = node_map[curr.next]  # lookup copied next node from hashmap
	copied_curr_rand = node_map[curr.random]  # lookup copied random node from hashmap
	# connect the pointers for the copied node
	copied_curr.next = copied_curr_next  # link the next pointer
	copied_curr.random = copied_curr_rand  # link the random pointer
	curr = curr.next  # move curr forward

Eventually it will look like this.

Complete Code Snippet

"""
# 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 copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
		# Fisrt Pass: Copy the nodes and Save them in a HashMap/Dictionary
		node_map = {None: None}  # Adding None to skip handling NULL Pointers
		curr = head
		while curr:
			node_map[curr] = Node(curr.val)
			curr = curr.next
		
		# Second Pass: Connect the pointers
		curr = head
		while curr:
			# lookup copied node from hashmap
			curr_copied = node_map[curr]
			# connect the pointers for the copied node
			curr_copied.next = node_map[curr.next]
			curr_copied.random = node_map[curr.random]
			# move curr forward
			curr = curr.next
		
		return nodeMap[head]  # head of the new copied linked list

Thanks for Stopping by! Happy Leet coding.

Connect with me on