# 138. Copy List with Random Pointer

Updated: 2023-05-24

LeetCode problem

The problem asks to create a deep copy of a given linked list with a random pointer in each node. A deep copy means that the new linked list will have completely new nodes, and none of its pointers should point to the nodes in the original list. Both the next and random pointers of the new nodes should point to the new nodes in the copied list in the same order as the original list.

Naive Solution:

A naive solution would be to first create a copy of the original linked list without the random pointers.

Then, for each node in the copied list, search for the node in the original list that its random pointer is pointing to, and update the random pointer in the copied list accordingly.

This solution would take O(n^2) time complexity, as we need to search for the random node for each node in the copied list.

Logic:

1. Initialize a hashmap to store the mapping of original nodes to new nodes
2. Iterate through the original list to create new nodes and add their mappings to the hashmap
3. Iterate through the original list again to update the next and random pointers of the new nodes using the hashmap

Solution:

class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
return None

nodes = {}

nodes[cur] = new_cur

while cur:  # create mapping old-new linked nodes
node = Node(cur.val)
nodes[cur] = node
cur = cur.next

while cur:
if cur.next:
nodes[cur].next = nodes[cur.next]
if cur.random:
nodes[cur].random = nodes[cur.random]

cur = cur.next