No. 138 - Copy List with Random Pointer
====
---
## [LeetCode 138 -- 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`.
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.
Example 1.
```
Input: head = [[13,null],[2,3],[6,1],[5,1]]
Output: [[13,null],[2,3],[6,1],[5,1]]
```
---
這一次我們提供兩種不同的思路:
### 解法 1.
第一種解法我們將原本的 linked list 的長度增長為一倍，每一個原本的 node 後面會接一個複製後的 node 也就是說原本的 linked list 會變成下圖所示:
```cpp=
Node *node = head;
Node *copy;
while (node) {
copy = new Node(node->val);
copy->next = node->next;
node->next = copy;
node = copy->next;
}
```
將所有 nodes 都複製一便並接上之後，接著我們在重新尋訪一遍新的 linked list，不過我們並不用一個一個尋訪，而是兩個兩個尋訪。這一次的尋訪是為了把複製的 nodes 的 `random` 指標指向對應的複製的 node。這步驟的做法如下:
```cpp=
node = head;
while (node) {
copy = node->next;
if (node->random)
copy->random = node->random->next;
node = copy->next;
}
```
經過上面的做法後 linked list 會如下圖所示:
接著我們再把複製的 nodes 跟原本的 nodes 分離成兩串 linked list
```cpp=
node = head;
result = head->next;
while (node) {
copy = node->next;
node->next = copy->next;
if (copy->next)
copy->next = copy->next->next;
node = node->next;
}
```
上面的程式碼將 linked list 兩個兩個走訪一遍後就會拆出由複製 nodes 組成的 linked list 以及還原原本的 linked list
完整的程式碼如下:
```cpp=
/*
// 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 head;
Node *node = head;
Node *copy;
Node *result;
while (node) {
copy = new Node(node->val);
copy->next = node->next;
node->next = copy;
node = copy->next;
}
node = head;
while (node) {
copy = node->next;
if (node->random)
copy->random = node->random->next;
node = copy->next;
}
node = head;
result = head->next;
while (node) {
copy = node->next;
node->next = copy->next;
if (copy->next)
copy->next = copy->next->next;
node = node->next;
}
return result;
}
};
```
### 解法 2.
第二種解法我們將使用到 hash table 的資料結構。C++ STL library 中的 `unordered_map` 就是對應 hash table 的資料結構。
首先我們先宣告一個 `node_table` 的 hash table，這個 hash table 的 `key, value` 分別是原本 linked list 的 node 以及複製後的 node。
接著我們便依序尋訪每個 linked list 的 node，每次的尋訪我們就要看 `node_table` 是否已經有紀錄這個 node。若沒有，則需把當前的 node 跟其複製的 node 加入 `node_table`。
每次尋訪的 node 都一定會有一個複製的 node，不論是已經在 hash table 裡還是剛複製，我們在每次尋訪要做的事就是將這個 node 的複製 node 的 `next` 以及 `random` 指標指向對應原本的 nodes 的複製 node。
所以訪問一個 node 需要思考三件事:
1. 當前訪問的 node 是否已經在 `node_table` 中
```cpp=
if (node_table.find(node) == node_table.end()) {
copy = new Node(node->val);
node_table.insert(pair(node, copy));
}
else
copy = node_table[node];
```
2. 當前訪問的 node 的 `next` 指向的 node 是否已經在 `node_table` 中
```cpp=
if (node_table.find(node->next) == node_table.end()) {
copy->next = new Node(node->next->val);
node_table.insert(pair(node->next, copy->next));
}
else
copy->next = node_table[node->next];
```
3. 當前訪問的 node 的 `random` 指向的 node 是否已經在 `node_table` 中
```cpp=
if (node_table.find(node->random) == node_table.end()) {
copy->random = new Node(node->random->val);
node_table.insert(pair(node->random, copy->random));
}
else
copy->random = node_table[node->random];
```
由此，我們可以在每次訪問一個 node 時就同時把它的複製的 node 本身及其 `next` 跟 `random` 指標指的 node 的複製 node 都加入 hash table 並且同時接好。
完整的程式碼如下:
```cpp=
unordered_map<Node*, Node*> node_table;
Node *node = head;
while (node) {
Node *copy;
if (node_table.find(node) == node_table.end()) {
copy = new Node(node->val);
node_table.insert(pair(node, copy));
}
else
copy = node_table[node];
if (node->next) {
if (node_table.find(node->next) == node_table.end()) {
copy->next = new Node(node->next->val);
node_table.insert(pair(node->next, copy->next));
}
else
copy->next = node_table[node->next];
}
if (node->random) {
if (node_table.find(node->random) == node_table.end()) {
copy->random = new Node(node->random->val);
node_table.insert(pair(node->random, copy->random));
}
else
copy->random = node_table[node->random];
}
node = node->next;
}
```
### 複雜度分析
第一解法我們需要重複走訪 linked list 3 次。雖然第二跟第三次走訪的 linked list 是原本的兩倍長，但實際上這兩次仍然只走了原本 linked list 的長度 (因為是兩兩走訪)，所以時間複雜度是 $O(N)$。
而第一個解法的空間複雜度，因為需要複製所有 linked list 的 nodes 所以需要 $O(N)$。
第二個解法我們只需要走訪 linked list 1 次即可，所以時間複雜度是 $O(N)$。
而在空間複雜度上需要 hash table 的資料結構所以需要額外的空間。
Sign in with Wallet
Connect another wallet