304 North Cardinal St.
Dorchester Center, MA 02124

# Copy List with Random Pointer LeetCode Solution

## Problem – Copy List with Random Pointer

A linked list of length `n` is given such that each node contains an additional random pointer, which could point to any node in the list, or `null`.

Construct a deep copy of the list. The deep copy should consist of exactly `n` brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the `next` and `random` pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes `X` and `Y` in the original list, where `X.random --> Y`, then for the corresponding two nodes `x` and `y` in the copied list, `x.random --> y`.

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`) that the `random` pointer points to, or `null` if it does not point to any node.

Your code will only be given the `head` of the original linked list.

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 = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
``````

Constraints:

• `0 <= n <= 1000`
• `-104 <= Node.val <= 104`
• `Node.random` is `null` or is pointing to some node in the linked list.

### Copy List with Random Pointer LeetCode Solution in Java

``````public RandomListNode copyRandomList(RandomListNode head) {

// First round: make copy of each node,
// and link them together side-by-side in a single list.
while (iter != null) {
next = iter.next;

RandomListNode copy = new RandomListNode(iter.label);
iter.next = copy;
copy.next = next;

iter = next;
}

// Second round: assign random pointers for the copy nodes.
while (iter != null) {
if (iter.random != null) {
iter.next.random = iter.random.next;
}
iter = iter.next.next;
}

// Third round: restore the original list, and extract the copy list.

while (iter != null) {
next = iter.next.next;

// extract the copy
copy = iter.next;
copyIter.next = copy;
copyIter = copy;

// restore the original list
iter.next = next;

iter = next;
}

}
``````

### Copy List with Random Pointer LeetCode Solution in C++

``````class Solution {
public:
map<Node*, Node*> m;
int i=0;
while (ptr) {
m[ptr] =new Node(ptr->val);
ptr = ptr->next;
}
while (ptr) {
m[ptr]->next = m[ptr->next];
m[ptr]->random = m[ptr->random];
ptr = ptr->next;
}
}
};
``````

### Copy List with Random Pointer LeetCode Solution in Python

``````def copyRandomList1(self, head):
return
# copy nodes
while cur:
nxt = cur.next
cur.next = RandomListNode(cur.label)
cur.next.next = nxt
cur = nxt
# copy random pointers
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# separate two parts
while cur.next:
cur = cur.next
return second

# using dictionary
return
# copy nodes
while cur:
dic[cur] = RandomListNode(cur.label)
cur = cur.next
# copy random pointers
while cur:
if cur.random:
dic[cur].random = dic[cur.random]
if cur.next:
dic[cur].next = dic[cur.next]
cur = cur.next
``````
##### Copy List with Random Pointer LeetCode Solution Review:

In our experience, we suggest you solve this Copy List with Random Pointer LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Copy List with Random Pointer LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Copy List with Random Pointer LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions