LeetCode 0138. Copy List with Random Pointer Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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]]

 

Constraints:

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

Solutions

Solution 1: Hash Table

We can define a dummy head node dummy and use a pointer tail to point to the dummy head node. Then, we traverse the linked list, copying each node and storing the mapping between each node and its copy in a hash table d, while also connecting the next pointers of the copied nodes.

Next, we traverse the linked list again and use the mappings stored in the hash table to connect the random pointers of the copied nodes.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.

PythonJavaC++GoTypeScriptJavaScriptC#

""" # 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: "Optional[Node]") -> "Optional[Node]": d = {} dummy = tail = Node(0) cur = head while cur: node = Node(cur.val) tail.next = node tail = tail.next d[cur] = node cur = cur.next cur = head while cur: d[cur].random = d[cur.random] if cur.random else None cur = cur.next return dummy.next(code-box)

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { Map<Node, Node> d = new HashMap<>(); Node dummy = new Node(0); Node tail = dummy; for (Node cur = head; cur != null; cur = cur.next) { Node node = new Node(cur.val); tail.next = node; tail = node; d.put(cur, node); } for (Node cur = head; cur != null; cur = cur.next) { d.get(cur).random = cur.random == null ? null : d.get(cur.random); } return dummy.next; } }(code-box)

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { Node* dummy = new Node(0); Node* tail = dummy; unordered_map<Node*, Node*> d; for (Node* cur = head; cur; cur = cur->next) { Node* node = new Node(cur->val); tail->next = node; tail = node; d[cur] = node; } for (Node* cur = head; cur; cur = cur->next) { d[cur]->random = cur->random ? d[cur->random] : nullptr; } return dummy->next; } };(code-box)

/** * Definition for a Node. * type Node struct { * Val int * Next *Node * Random *Node * } */ func copyRandomList(head *Node) *Node { dummy := &Node{} tail := dummy d := map[*Node]*Node{} for cur := head; cur != nil; cur = cur.Next { node := &Node{Val: cur.Val} d[cur] = node tail.Next = node tail = node } for cur := head; cur != nil; cur = cur.Next { if cur.Random != nil { d[cur].Random = d[cur.Random] } } return dummy.Next }(code-box)

/** * Definition for _Node. * class _Node { * val: number * next: _Node | null * random: _Node | null * * constructor(val?: number, next?: _Node, random?: _Node) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * this.random = (random===undefined ? null : random) * } * } */ function copyRandomList(head: _Node | null): _Node | null { const d: Map<_Node, _Node> = new Map(); const dummy = new _Node(); let tail = dummy; for (let cur = head; cur; cur = cur.next) { const node = new _Node(cur.val); tail.next = node; tail = node; d.set(cur, node); } for (let cur = head; cur; cur = cur.next) { d.get(cur)!.random = cur.random ? d.get(cur.random)! : null; } return dummy.next; }(code-box)

/** * // 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) { const d = new Map(); const dummy = new _Node(); let tail = dummy; for (let cur = head; cur; cur = cur.next) { const node = new _Node(cur.val); tail.next = node; tail = node; d.set(cur, node); } for (let cur = head; cur; cur = cur.next) { d.get(cur).random = cur.random ? d.get(cur.random) : null; } return dummy.next; };(code-box)

/* // 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 { public Node CopyRandomList(Node head) { Dictionary<Node, Node> d = new Dictionary<Node, Node>(); Node dummy = new Node(0); Node tail = dummy; for (Node cur = head; cur != null; cur = cur.next) { Node node = new Node(cur.val); tail.next = node; tail = node; d[cur] = node; } for (Node cur = head; cur != null; cur = cur.next) { if (cur.random != null) { d[cur].random = d[cur.random]; } } return dummy.next; } }(code-box)

Solution 2: Simulation (Space Optimization)

In Solution 1, we used an additional hash table to store the mapping between the original nodes and the copied nodes. We can also achieve this without using extra space, as follows:

1. Traverse the original linked list, and for each node, create a new node and insert it between the original node and the original node's next node.
2. Traverse the linked list again, and set the random pointer of the new node based on the random pointer of the original node.
3. Finally, split the linked list into the original linked list and the copied linked list.

The time complexity is O(n), where n is the length of the linked list. Ignoring the space occupied by the answer linked list, the space complexity is O(1).

PythonJavaC++GoTypeScriptJavaScriptC#

""" # 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: "Optional[Node]") -> "Optional[Node]": if head is None: return None cur = head while cur: node = Node(cur.val, cur.next) cur.next = node cur = node.next cur = head while cur: cur.next.random = cur.random.next if cur.random else None cur = cur.next.next cur = head ans = head.next while cur.next: node = cur.next cur.next = node.next cur = node return ans(code-box)

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ public class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } Node cur = head; while (cur != null) { Node node = new Node(cur.val); node.next = cur.next; cur.next = node; cur = node.next; } cur = head; while (cur != null) { cur.next.random = cur.random == null ? null : cur.random.next; cur = cur.next.next; } cur = head; Node ans = head.next; while (cur.next != null) { Node node = cur.next; cur.next = node.next; cur = node; } return ans; } }(code-box)

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if (!head) { return nullptr; } Node* cur = head; while (cur != nullptr) { Node* node = new Node(cur->val); node->next = cur->next; cur->next = node; cur = node->next; } cur = head; while (cur != nullptr) { cur->next->random = cur->random == nullptr ? nullptr : cur->random->next; cur = cur->next->next; } cur = head; Node* ans = head->next; while (cur->next != nullptr) { Node* node = cur->next; cur->next = node->next; cur = node; } return ans; } };(code-box)

/** * Definition for a Node. * type Node struct { * Val int * Next *Node * Random *Node * } */ func copyRandomList(head *Node) *Node { if head == nil { return nil } for cur := head; cur != nil; { node := &Node{cur.Val, cur.Next, nil} cur.Next = node cur = node.Next } for cur := head; cur != nil; cur = cur.Next.Next { if cur.Random != nil { cur.Next.Random = cur.Random.Next } } ans := head.Next for cur := head; cur.Next != nil; { node := cur.Next cur.Next = node.Next cur = node } return ans }(code-box)

/** * Definition for _Node. * class _Node { * val: number * next: _Node | null * random: _Node | null * * constructor(val?: number, next?: _Node, random?: _Node) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * this.random = (random===undefined ? null : random) * } * } */ function copyRandomList(head: _Node | null): _Node | null { if (head === null) { return null; } let cur = head; while (cur !== null) { const node = new _Node(cur.val); node.next = cur.next; cur.next = node; cur = node.next; } cur = head; while (cur !== null) { cur.next.random = cur.random === null ? null : cur.random.next; cur = cur.next.next; } cur = head; const ans = head.next; while (cur.next !== null) { const node = cur.next; cur.next = node.next; cur = node; } return ans; }(code-box)

/** * // 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 === null) { return null; } let cur = head; while (cur !== null) { const node = new _Node(cur.val); node.next = cur.next; cur.next = node; cur = node.next; } cur = head; while (cur !== null) { cur.next.random = cur.random === null ? null : cur.random.next; cur = cur.next.next; } cur = head; const ans = head.next; while (cur.next !== null) { const node = cur.next; cur.next = node.next; cur = node; } return ans; };(code-box)

/* // 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 { public Node CopyRandomList(Node head) { if (head == null) { return null; } Node cur = head; while (cur != null) { Node node = new Node(cur.val); node.next = cur.next; cur.next = node; cur = node.next; } cur = head; while (cur != null) { cur.next.random = cur.random == null ? null : cur.random.next; cur = cur.next.next; } cur = head; Node ans = head.next; while (cur.next != null) { Node node = cur.next; cur.next = node.next; cur = node; } return ans; } }(code-box)