deep copy random list

gistfile1.cpp

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
 
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        //copy each node to new list, and keep old value of random* pointer (to be updated later)
        unordered_map<RandomListNode *, RandomListNode*> oldMapToNew;
        RandomListNode * front = head;
        RandomListNode *newHead = NULL;
        RandomListNode *newTail = NULL;
        while (front) {
            RandomListNode *newNode  = new RandomListNode(front->label);
            newNode->random = front->random;    //old, to be updated to new
            oldMapToNew[front] = newNode;
            if (!newHead) {
                newHead = newNode; 
                newTail = newHead;
            }
            else {
                newTail->next = newNode;
                newTail = newNode;
            }
            front = front->next;
        }
        
        
        //update random pointer
        front = newHead;
        while (front) {
            unordered_map<RandomListNode *, RandomListNode*>::iterator it = oldMapToNew.find(front->random);
            if (it != oldMapToNew.end())
                front->random = it->second;
            front = front->next;
        }
        return newHead;
    }
};