138. 复制带随机指针的链表

 1 /*
 2 // Definition for a Node.
 3 class Node {
 4 public:
 5     int val;
 6     Node* next;
 7     Node* random;
 8     
 9     Node(int _val) {
10         val = _val;
11         next = NULL;
12         random = NULL;
13     }
14 };
15 */
16 
17 class Solution 
18 {
19 public:
20     Node* copyRandomList(Node* head) 
21     {
22         unordered_map<Node*, Node*> Map;
23         Node* cur = head;
24         while (cur != NULL)
25         {
26             Map[cur] = new Node(cur->val);
27             cur = cur->next;
28         }
29 
30         cur = head;
31         while (cur != NULL)
32         {
33             Map[cur]->next = Map[cur->next];
34             Map[cur]->random = Map[cur->random];
35             cur = cur->next;
36         }
37         return Map[head];
38     }
39 };