Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

tag: hashtable, linked-list

虽然被标记为hard，但代码不长。

问题关键是，在拷贝完next指针后，要根据原来链表中的random的地址，找到新建的链表中对应的node的地址，这里我们用一个hashtable来实现，在拷贝next指针时，将对应关系记录下来。

空间复杂度o(n)，时间复杂度o(n)。

/**
 * 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:
    unordered_map<RandomListNode *, RandomListNode *> hashTable;
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode * superHeadOld = new RandomListNode(0);
        RandomListNode * superHeadNew = new RandomListNode(0);
        superHeadOld->next = head;
        RandomListNode * p = superHeadOld;
        RandomListNode * np = superHeadNew;
        while(p->next != NULL){
            np->next = new RandomListNode(p->next->label);
            hashTable[p->next] = np->next;
            p = p->next;
            np = np->next;
        }
        p = head;
        np = superHeadNew->next;
        while(p != NULL){
            if(p->random != NULL){
                np->random = hashTable[p->random];
            }
            p = p->next;
            np = np->next;
        }
        np = superHeadNew->next;
        delete superHeadNew;
        delete superHeadOld;
        return np;
    }
};