給你一個長度為?n?的鏈表，每個節點包含一個額外增加的隨機指針?random?，該指針可以指向鏈表中的任何節點或空節點。
構造這個鏈表的?深拷貝。?深拷貝應該正好由?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?作為傳入參數。
示例 1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
輸入：head = [[1,1],[2,1]] 輸出：[[1,1],[2,1]]
示例 3：
輸入：head = [[3,null],[3,0],[3,null]] 輸出：[[3,null],[3,0],[3,null]]
/*
// 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: unordered_map<Node* ,Node*>cacheNnode;Node* copyRandomList(Node* head) {if(head==nullptr){return nullptr;}if(!cacheNnode.count(head)){Node*headNew=new Node(head->val);cacheNnode[head]=headNew;headNew->next=copyRandomList(head->next);headNew->random=copyRandomList(head->random);}return cacheNnode[head];}
};對一個特殊的鏈表進行深拷貝。如果是普通鏈表，我們可以直接按照遍歷的順序創建鏈表節點。而本題中因為隨機指針的存在，當我們拷貝節點時，「當前節點的隨機指針指向的節點」可能還沒創建，因此我們需要變換思路。一個可行方案是，我們利用回溯的方式，讓每個節點的拷貝操作相互獨立。對于當前節點，我們首先要進行拷貝，然后我們進行「當前節點的后繼節點」和「當前節點的隨機指針指向的節點」拷貝，拷貝完成后將創建的新節點的指針返回，即可完成當前節點的兩指針的賦值。
具體地，我們用哈希表記錄每一個節點對應新節點的創建情況。遍歷該鏈表的過程中，我們檢查「當前節點的后繼節點」和「當前節點的隨機指針指向的節點」的創建情況。如果這兩個節點中的任何一個節點的新節點沒有被創建，我們都立刻遞歸地進行創建。當我們拷貝完成，回溯到當前層時，我們即可完成當前節點的指針賦值。注意一個節點可能被多個其他節點指向，因此我們可能遞歸地多次嘗試拷貝某個節點，為了防止重復拷貝，我們需要首先檢查當前節點是否被拷貝過，如果已經拷貝過，我們可以直接從哈希表中取出拷貝后的節點的指針并返回即可。
)
