# LeetCode 138. Copy List with Random Pointer

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

The Linked List is represented in the input/output as a list of `n` nodes. Each node is represented as a pair of `[val, random_index]` where:

• `val`: an integer representing `Node.val`
• `random_index`: the index of the node (range from `0` to `n-1`) where random pointer points to, or `null` if it does not point to any node.

Example 1:

```Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
```

Example 2:

```Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
```

Example 3:

```Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
```

Example 4:

```Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.
```

Constraints:

• `-10000 <= Node.val <= 10000`
• `Node.random` is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.

## Explanation

We can introduce a map to help us store the relationship between the original list node and the copy version new node.

Whenever we visited an original node, we can check if we have already created a copy version. If created, we use copy version to generate corresponding position new node in the new linked list.

## Java Solution

``````/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
return null;
}

Map<RandomListNode, RandomListNode> map = new HashMap<>();

RandomListNode dummy = new RandomListNode(0);
RandomListNode current = dummy;
RandomListNode newNode = null;

} else {
}

} else {
}
}

current.next = newNode;
current = newNode;
}

return dummy.next;
}
}``````

## Python Solution

``````"""
# 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':
return None

mapping = {}

while current != None:
mapping[current] = Node(current.val)
current= current.next

for node in mapping:
if node.next:
mapping[node].next = mapping[node.next]
if node.random:
mapping[node].random = mapping[node.random]