Copy List With Random Pointer - Leetcode Solution

Problem description:

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

Example: Input: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Solution:

The given linked list contains random pointers, which means that each node can point to any node in the list. To create a deep copy of this linked list, we need to copy each node and its random pointer.

To solve this problem, we can use a hash table to store the created nodes. We iterate through the input linked list and create a new node for each node encountered. We add the new node to the hash table. Then we copy the next and random pointers of the original node to the new node. If the next or random pointer of the original node is null, we assign it to null. If the next or random pointer of the original node points to a node that has not been created yet, we create the node and add it to the hash table. If the next or random pointer of the original node points to a node that has already been created, we use the corresponding node in the hash table.

At the end of the iteration, we return the head of the deep copy linked list.

Code:

/**

• Definition for a Node.
• function Node(val,next,random) {
• this.val = val;
• this.next = next;
• this.random = random;
• }; / /*
• @param {Node} head
• @return {Node} */ var copyRandomList = function(head) { if (!head) { return null; } const map = new Map(); let curr = head; while (curr) { const newNode = new Node(curr.val, null, null); map.set(curr, newNode); curr = curr.next; } curr = head; while (curr) { const newNode = map.get(curr); newNode.next = map.get(curr.next) || null; newNode.random = map.get(curr.random) || null; curr = curr.next; } return map.get(head); };

Explanation:

In the above solution, we first check for the base case when the head is null. Then we create an empty hash table to store the created nodes. We initialize the current node to the head of the input linked list.

We then iterate through the input linked list and create a new node for each node encountered. We add the new node to the hash table using the original node as the key. Then we move to the next node in the input linked list.

Next, we iterate through the input linked list again and copy the next and random pointers of each node to the corresponding new node. We check whether the next or random pointer of the original node is null or not. If it is not null, we check whether the next or random node has already been created or not. If it has not been created, we create a new node and add it to the hash table. If it has been created, we use the corresponding node in the hash table.

Finally, we return the head of the deep copy linked list, which is the node corresponding to the head of the input linked list in the hash table.

1