# Solution For Copy List With Random Pointer

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;
* };
*/
/

* @return {Node}
*/
return null;
}
const map = new Map();
while (curr) {
const newNode = new Node(curr.val, null, null);
map.set(curr, newNode);
curr = curr.next;
}
while (curr) {
const newNode = map.get(curr);
newNode.next = map.get(curr.next) || null;
newNode.random = map.get(curr.random) || null;
curr = curr.next;
}
};

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.

## Step by Step Implementation For Copy List With Random Pointer

```/**
* // Definition for a Node.
* class Node {
*     int val;
*     Node next;
*     Node random;
*     Node() {}
*     Node(int val) { this.val = val; }
*     Node(int val, Node next, Node random) {
*         this.val = val;
*         this.next = next;
*         this.random = random;
*     }
* }
*/

class Solution {
if (head == null) return null;

// create copies of each node and link them together in a new list
while (curr != null) {
Node copy = new Node(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}

// set random pointers for each node in new list
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}

// split new list from old list
while (curr != null) {
Node temp = curr.next;
curr.next = temp.next;
if (temp.next != null) temp.next = temp.next.next;
curr = curr.next;
}
}
}```
```# 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: 'Node') -> 'Node':
# if head is None, return None
return None

# create a dictionary to store the old nodes as keys and new nodes as values
nodes_dict = dict()

# create a new node with the same value as head

# set the key as head and value as new_head in the dictionary

# set head to head.next (move to the next node in the list)

# create a new node to keep track of the new list

# iterate through the list until head is None
# create a new node with the same value as head

# set the key as head and the value as new_node.next in the dictionary

# set head to head.next (move to the next node in the list)

# set new_node to new_node.next (move to the next node in the new list)
new_node = new_node.next

# iterate through the new list until head is None
# if the current node has a random node
# set the current node's random node to the node in the dictionary with the same value as the current node's random node

# set head to head.next (move to the next node in the list)

```/**
* // Definition for a Node.
* function Node(val,next,random) {
*    this.val = val;
*    this.next = next;
*    this.random = random;
* };
*/
/**
* @return {Node}
*/

// Edge case - if head is null, return null
return null;
}

// Create a map to store old nodes as keys and new nodes as values
let map = new Map();

// Set pointers for the new head

// Iterate through the list
while(oldCurr.next) {

// Set next for the new node
newCurr.next = new Node(oldCurr.next.val);

// Set random for the new node if it exists
if(oldCurr.random) {
newCurr.random = new Node(oldCurr.random.val);
}

// Set the key of the old node's next to be the old node's next
map.set(oldCurr.next, newCurr.next);

// Move old and new pointers
oldCurr = oldCurr.next;
newCurr = newCurr.next;
}

// Set random for the last new node if it exists
if(oldCurr.random) {
newCurr.random = new Node(oldCurr.random.val);
}

// Iterate through the map
for(let [oldNode, newNode] of map) {

// Set random for each new node using the map
if(oldNode.random) {
newNode.random = map.get(oldNode.random);
}
}

};```
```/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
*     int label;
*     RandomListNode *next, *random;
*     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
//copy next pointers
while(node!=NULL){
RandomListNode *temp = new RandomListNode(node->label);
temp->next = node->next;
node->next = temp;
node = node->next->next;
}
//copy random pointers
while(node!=NULL){
if(node->random != NULL)
node->next->random = node->random->next;
node = node->next->next;
}
//restore next pointers
while(node != NULL){
RandomListNode *temp = node->next;
node->next = temp->next;
if(temp->next != NULL) temp->next = temp->next->next;
node = node->next;
}
return copy;
}
};```
```/**
* Definition for a Node.
* public class Node {
*     public int val;
*     public Node next;
*     public Node random;
*     public Node(int _val) {
*         val = _val;
*         next = null;
*         random = null;
*     }
* }
*/
public class Solution {
// Create a dictionary to store old nodes as keys and new nodes as values
Dictionary map = new Dictionary();

// Iterate through the old list, creating new nodes along the way and storing them in the map
while (curr != null) {
curr = curr.next;
}

// Reset curr to the head of the old list

// Iterate through the old list again, this time assigning next and random pointers for each new node
while (curr != null) {
map[curr].next = map.ContainsKey(curr.next) ? map[curr.next] : null;
map[curr].random = map.ContainsKey(curr.random) ? map[curr.random] : null;
curr = curr.next;
}

// Return the head of the new list