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.

C++:
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 }
Advertisements
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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s