138. Copy List with Random Pointer
給定一個長度為 n 的鏈表，每個節點包含一個額外的隨機指針，該指針可以指向鏈表中的任何節點，或者為 null。
構建這個鏈表的深拷貝。深拷貝應該包含正好 n 個全新的節點，每個新節點的值設置為其對應的原始節點的值。新節點的 next 和 random 指針應該指向新鏈表中的新節點，使得原始鏈表和拷貝鏈表中的指針表示相同的鏈表狀態。新鏈表中的指針不能指向原始鏈表中的節點。
例如，如果在原始鏈表中有兩個節點 X 和 Y，其中 X.random --> Y，那麼在拷貝鏈表中對應的兩個節點 x 和 y 應該有 x.random --> y。
返回拷貝鏈表的頭節點。
在輸入/輸出中，鏈表表示為 n 個節點的列表。每個節點表示為 [val, random_index] 的一對，其中：val：表示 Node.val 的整數
random_index：隨機指針指向的節點的索引（範圍從 0 到 n-1），如果不指向任何節點則為 null。
你的代碼將只給定原始鏈表的頭節點。
範例：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
Python
# 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 not head:
return None
# Create a hash map to map original nodes to their copies
old_to_new = {}
# Step 1: Create all nodes and populate the hash map
current = head
while current:
old_to_new[current] = Node(current.val)
current = current.next
# Step 2: Assign next and random pointers
current = head
while current:
if current.next:
old_to_new[current].next = old_to_new[current.next]
if current.random:
old_to_new[current].random = old_to_new[current.random]
current = current.next
# Return the head of the copied linked list
return old_to_new[head]
17.34MB, 33ms
C++
#include <unordered_map>
using namespace std;
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
unordered_map<Node*, Node*> oldToNew;
// Step 1: Create all nodes and populate the hash map
Node* current = head;
while (current) {
oldToNew[current] = new Node(current->val);
current = current->next;
}
// Step 2: Assign next and random pointers
current = head;
while (current) {
if (current->next) {
oldToNew[current]->next = oldToNew[current->next];
}
if (current->random) {
oldToNew[current]->random = oldToNew[current->random];
}
current = current->next;
}
// Return the head of the copied linked list
return oldToNew[head];
}
};
13.43MB, 5ms
Javascript
/**
* @param {_Node} head
* @return {_Node}
*/
var copyRandomList = function(head) {
if (head === null) {
return null;
}
const oldToNew = new Map();
// Step 1: Create all nodes and populate the hash map
let current = head;
while (current !== null) {
oldToNew.set(current, new _Node(current.val, null, null));
current = current.next;
}
// Step 2: Assign next and random pointers
current = head;
while (current !== null) {
if (current.next !== null) {
oldToNew.get(current).next = oldToNew.get(current.next);
}
if (current.random !== null) {
oldToNew.get(current).random = oldToNew.get(current.random);
}
current = current.next;
}
// Return the head of the copied linked list
return oldToNew.get(head);
};
51.28MB, 67ms
