步骤:由于涉及到深拷贝,除了next指针还有random指针。random指针寻找定位,将对应的关系复制比较困难。哈希表关联容器上。
1)unorder_map<node*,node*> mp:实现复制与深拷贝后----对应的节点
2)刚开始的深拷贝,将原先的节点深拷贝后的儿子放入map与其父亲-----对应
mp[t] = new Node(t->val);//将复制后的节点放入map,与原节点一一对应,此时仅仅复制了值,没有确定指针关系,此时为浅拷贝,因为多个指针指向同一个节点
3)next与random指针的复制对应关系
mp[t]->next = mp[t->next]; mp[t]->random = mp[t->random];//解决指针指向关系,通过原指针作为索引获取下一个节点指向。
1 //节点有两个指针一个值 2 class Solution{ 3 public: 4 Node* copyRandomList(Node* head) { 5 if(NULL == head) return head; 6 unorder_map<Node*,Node*> mp; 7 Node* t = head; 8 while (t != NULL){ 9 mp[t] = new Node(t->val); 10 t = t->next; 11 } 12 t = head; 13 while(t != NULL){ 14 if(t->next) 15 mp[t]->next = mp[t->next]; 16 if(t->random) 17 mp[t]->random = mp[t->random]; 18 t = t->next; 19 } 20 return mp[head] 21 } 22 };