Deep Copy

code

// Example program
#include <iostream>
#include <string>
#include <map>

using namespace std;

class node {
public:
    int val;
    node* next;
    node* random;
    node (int val)
    {
        this->val = val;
        this->next = NULL;
        this->random = NULL;
    }
};

node* deepcopy(node* root)
{
    if(root == NULL)
    {
        return NULL;   
    }

    node* p = root;
    map<node*, node*> hash;
    while(p != NULL)
    {
        node* newnode = new node(p->val);
        hash[p] = newnode;
        p = p->next;
    }

    p = root;
    while(p != NULL)
    {
        hash[p]->next = hash[p->next];
        hash[p]->random = hash[p->random];
        p = p->next;
    }

    return hash[root];
}

https://leetcode.com/problems/copy-list-with-random-pointer/