1. 題目描述

這題題意感覺說的不是很清楚，容易讓人產生歧義！其實題意很簡單，給你一個鏈表 head，你深拷貝它，然后返回即可，注意不能修改原鏈表

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/

2. 坑

首先，這題絕對沒你看上去的那么簡單，復制鏈表？太簡單了，不就是鏈表的創建嗎？
不！本題有一個有意思的地方，就是它有一個隨機指針，隨機指針以為著什么？
意味著，它指向的節點，可能還未創建！
因此說，我們不能直接遍歷鏈表，來創建新鏈表，需要一些特殊方法

3. 思路1 – 哈希表

$O(N)$時間， $O(N)$空間

思路呢，也很簡單，既然隨機指針可能指向一個還未創建的節點，那么我們就先創建它，然后通過哈希表存起來，并與原鏈表的相應節點做映射。
這樣，當我們下次遍歷到這個隨機節點時，我們可以檢查一下哈希表，看看是否已經建立過了，避免重復創建節點。

代碼

// 本題的難點主要在于，當我們需要將指針指向某個節點時
// 隨機指針指向的節點可能還不存在
class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;Node *dummy = new Node(-1);Node *cur = dummy;// refto 存儲的是，原鏈表head與它的拷貝之間的映射unordered_map<Node*, Node*> refto;while(head) { // 遍歷原鏈表的每一個節點，創建它自己和他的random指針指向的節點// 并讓它的random指針指向原鏈表random指針指向的節點if(refto[head] == nullptr) {Node *newNode = new Node(head->val);refto[head] = newNode;}if(head->random && refto[head->random] == nullptr) {Node *newNode = new Node(head->random->val);refto[head->random] = newNode;}refto[head]->random = refto[head->random];cur->next = refto[head];cur = refto[head];head = head->next;}return dummy->next;}
};

4. 思路2 – 原地修改

$O(N)$ 時間， $O(1)$空間。

參考題解，最后的動圖很易懂！
注意在計算空間復雜度時，是不考慮創建新鏈表產生的空間的，因為那是必須的，我們主要考慮的時額外空間的復雜度。

大體思路，只要看了題解中的動圖演示，基本就了解了，這里主要闡述一下流程：

1. 遍歷原鏈表，對于鏈表中的每個節點 $node$，在它的后面新創建一個新節點 $newNode$并插入到鏈表當中，即 $node$ ?? $newNode$ ?? $node$->$next$，這個 $newNode$ 就是對 $node$ 的深拷貝。（這一步就是核心所在，直接在原鏈表的基礎上創建新鏈表，然后再把它分離出來，太妙了！！）
2. 修改 $newNode$ 的 $random$ 指針。
3. 創建新鏈表的頭，修改 $newNode$ 的 $next$。

代碼

class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;// 原地拷貝for(Node *node = head; node != nullptr; node = node->next->next) {Node *newNode = new Node(node->val);// node -> newNode -> node.nextnewNode->next = node->next;node->next = newNode;}// 修改random指針for(Node *node = head; node != nullptr; node = node->next->next) {Node *newNode = node->next;// 判斷下randodm是否存在，存在的話，才有我們的copy// 注意要指向node->random->next而不是node->random// 因為node->random->next是我們自己創建的newNode->random = (node->random != nullptr) ? node->random->next : nullptr;}// 修改next指針以分離我們創建的鏈表Node *newHead = head->next;for(Node *node = head; node != nullptr; node = node->next) {Node *newNode = node->next;node->next = newNode->next; // 恢復原鏈表的next指針// 判斷下一個節點是否存在，存在的話，才有我們的copynewNode->next = (newNode->next != nullptr) ? newNode->next->next : nullptr; // 修改我們創建的鏈表的指針}return newHead;}
};