Last updated on October 5th, 2024 at 08:51 pm

Here, We see ** Copy List with Random Pointer LeetCode Solution**. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

*List of all LeetCode Solution*

*List of all LeetCode Solution*

## Topics

Hash Table, Linked List

## Companies

Amazon, Bloomberg, Microsoft, Uber

## Level of Question

Medium

**Copy List with Random Pointer LeetCode Solution**

## Table of Contents

**Problem Statement**

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`

.

Return *the head of the copied linked 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`

) 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 = [[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]]

**1. Copy List with Random Pointer LeetCode Solution C++**

class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; unordered_map<Node*, Node*> old_to_new; Node* curr = head; while (curr) { old_to_new[curr] = new Node(curr->val); curr = curr->next; } curr = head; while (curr) { old_to_new[curr]->next = old_to_new[curr->next]; old_to_new[curr]->random = old_to_new[curr->random]; curr = curr->next; } return old_to_new[head]; } };

**2. Copy List with Random Pointer LeetCode Solution Java**

public class Solution { public Node copyRandomList(Node head) { if (head == null) return null; HashMap<Node, Node> oldToNew = new HashMap<>(); Node curr = head; while (curr != null) { oldToNew.put(curr, new Node(curr.val)); curr = curr.next; } curr = head; while (curr != null) { oldToNew.get(curr).next = oldToNew.get(curr.next); oldToNew.get(curr).random = oldToNew.get(curr.random); curr = curr.next; } return oldToNew.get(head); } }

**3. Copy List with Random Pointer LeetCode Solution JavaScript**

var copyRandomList = function(head) { if (!head) return null; const oldToNew = new Map(); let curr = head; while (curr) { oldToNew.set(curr, new Node(curr.val)); curr = curr.next; } curr = head; while (curr) { oldToNew.get(curr).next = oldToNew.get(curr.next) || null; oldToNew.get(curr).random = oldToNew.get(curr.random) || null; curr = curr.next; } return oldToNew.get(head); };

**4. Copy List with Random Pointer Solution Python**

class Solution(object): def copyRandomList(self, head): if not head: return None old_to_new = {} curr = head while curr: old_to_new[curr] = Node(curr.val) curr = curr.next curr = head while curr: old_to_new[curr].next = old_to_new.get(curr.next) old_to_new[curr].random = old_to_new.get(curr.random) curr = curr.next return old_to_new[head]