学步园

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.

思路：

比起标准的链表深拷贝，还需要了解一个random pointer的信息。需要建立起新的链表单元和旧的链表单元之间的一一对应关系，然后将所有旧的random pointer更换为新的random pointer。这样就要求两次扫描，O(2n)。

题解：

/**
 * 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) {
        map<RandomListNode*, RandomListNode*> corresponding;
        corresponding[nullptr] = nullptr;
        
        RandomListNode* nhead = new RandomListNode(0);
        RandomListNode* last = nhead;
        RandomListNode* iter = head;
        
        // copy the original list
        while(iter != nullptr)
        {
            RandomListNode* new_node = new RandomListNode(iter->label);
            new_node->random = iter->random;
            last->next = new_node;
            
            corresponding[iter] = new_node;
            
            last = last->next;
            iter = iter->next;
        }
        
        // re-iterate to link the random pointer
        iter = nhead -> next;
        while(iter != nullptr)
        {
            iter->random = corresponding[iter->random];
            iter = iter->next;
        }
        
        iter = nhead;
        nhead = nhead->next;
        delete iter;
        return nhead;
    }
};