138. Copy List with Random Pointer

 1 /**
 2  * Definition for singly-linked list with a random pointer.
 3  * struct RandomListNode {
 4  *     int label;
 5  *     RandomListNode *next, *random;
 6  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     RandomListNode *copyRandomList(RandomListNode *head) {
12         if(head == NULL) return NULL;
13         unordered_map<RandomListNode*, RandomListNode*> old2new;
14         RandomListNode* tmp = head;
15         RandomListNode* dummy = new RandomListNode(-1);//从dummy开始，
16         RandomListNode* curr = dummy;//很容易建立next指针。curr的next指针只要指向current node即可
17         while(tmp){
18             RandomListNode* newnode = new RandomListNode(tmp -> label);
19             //newnode -> next
20             old2new[tmp] = newnode;
21             curr -> next = newnode;
22             curr = curr -> next;//curr也要往前走，才能完成整个链的链接
23             tmp = tmp -> next;
24         }
25         tmp = head;
26         while(tmp){
27             //old2new[tmp] -> next = old2new[tmp -> next];
28             if(tmp -> random){//要判断current node有无random指针
29                 old2new[tmp] -> random = old2new[tmp -> random];
30             }
31             tmp = tmp -> next;
32         }
33         return dummy -> next;//dummy不能变，否则return的就不是一整个链了
34     }
35 };