給你一個長度為 n 的鏈表，每個節(jié)點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。

構(gòu)造這個鏈表的 深拷貝。 深拷貝應(yīng)該正好由 n 個 全新 節(jié)點組成，其中每個新節(jié)點的值都設(shè)為其對應(yīng)的原節(jié)點的值。新節(jié)點的 next 指針和 random 指針也都應(yīng)指向復(fù)制鏈表中的新節(jié)點，并使原鏈表和復(fù)制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。復(fù)制鏈表中的指針都不應(yīng)指向原鏈表中的節(jié)點 。

例如，如果原鏈表中有 X 和 Y 兩個節(jié)點，其中 X.random --> Y 。那么在復(fù)制鏈表中對應(yīng)的兩個節(jié)點 x 和 y ，同樣有 x.random --> y 。

返回復(fù)制鏈表的頭節(jié)點。

用一個由 n 個節(jié)點組成的鏈表來表示輸入/輸出中的鏈表。每個節(jié)點用一個 [val, random_index] 表示：

val：一個表示 Node.val 的整數(shù)。 random_index：隨機指針指向的節(jié)點索引（范圍從 0 到 n-1）；如果不指向任何節(jié)點，則為 null 。

你的代碼 只 接受原鏈表的頭節(jié)點 head 作為傳入?yún)?shù)。

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

示例 4：

輸入：head = []
輸出：[]
解釋：給定的鏈表為空（空指針），因此返回 null。

提示：

0 <= n <= 1000 -10000 <= Node.val <= 10000 Node.random 為空（null）或指向鏈表中的節(jié)點。

代碼如下:

/* // 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==nullptr){return nullptr;}unordered_map<Node*,Node*>map;Node *newhead = new Node (head->val);map[head] = newhead;Node *pre = newhead;for (auto it = head->next;it!=nullptr;it = it->next){Node *cur = new Node(it->val);map[it] = cur;pre->next = cur;pre = cur;}for (auto it = head;it!=nullptr;it = it->next){map[it]->random = map[it->random];}return newhead;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 138 复制带随机指针的链表-中等的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。