Deep copy linked list

Do a deep copy of a linked list in which each item, in addition to the normal “next” pointer has a random pointer to another item in the list.

Sponsored: has published a chatbot, who can chat with you and help you find apartments in San Francisco and Bay area. Check it out:

01 Node* copyList(Node* head)
02 {
03     if(head==NULL)
04         return NULL;
05     Node* tmp=head;
06     int index=0;
07     map<Node*,int> m;
08     vector<Node*> v;
09     m[tmp]=index++;
10     Node* hd=new Node(head->val);
11     v.push_back(hd);
12     Node* prv=hd;
13     tmp=tmp->next;
14     while(tmp){
15         m[tmp]=index++;
16         Node* enode=new Node(tmp->val);
17         v.push_back(enode);
18         prv->next=enode;
19         prv=enode;
20         tmp=tmp->next;
21     }
22     tmp=hd;
23     while(tmp){
24         tmp->rand=v[m[head->rand]];
25         tmp=tmp->next;
26         head=head->next;
27     }
28     return hd;
29 }
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s