1 class Node { 2 public: 3 int val; 4 Node *next; 5 Node *random; 6 7 Node(int _val) : val(_val), next(NULL), random(NULL) {} 8 }; 9 10 class Solution { 11 public: 12 Node* copyRandomList(Node* head) { 13 map<Node *, int> node_map;//当前节点及其编号的映射 14 vector<Node *> node_vec; 15 Node *ptr = head; 16 17 int i = 0; 18 while (ptr) { //初始化 19 node_vec.push_back(new Node(ptr->val)); 20 node_map[ptr] = i; 21 ptr = ptr->next; 22 ++i; 23 } 24 node_vec.push_back(0); 25 26 ptr = head; 27 i = 0; 28 while (ptr) { 29 node_vec[i]->next = node_vec[i+1]; 30 if (ptr->random) { 31 int id = node_map[ptr->random]; 32 node_vec[i]->random = node_vec[id]; 33 } else { 34 node_vec[i]->random = NULL; 35 } 36 ptr = ptr->next; 37 ++i; 38 } 39 return node_vec[0]; 40 } 41 };
1 int main(int argc, const char * argv[]) { 2 Node a(1); 3 Node b(2); 4 Node c(3); 5 Node d(4); 6 Node e(5); 7 a.next = &b; 8 b.next = &c; 9 c.next = &d; 10 d.next = &e; 11 a.random = &c; 12 b.random = &d; 13 c.random = &c; 14 e.random = &d; 15 16 Solution solve; 17 Node *head = solve.copyRandomList(&a); 18 while (head) { 19 cout <<"head->val:" <<head->val <<‘ ‘; 20 if (head->random) { 21 cout <<"head->random->val:" <<head->random->val <<endl; 22 } else { 23 cout <<"head->random->NULL" <<endl; 24 } 25 head = head->next; 26 } 27 28 return 0; 29 }
原文：https://www.cnblogs.com/i-8023-/p/11826150.html
