/**
* 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) {
if (head == NULL) return NULL;
map<RandomListNode*, RandomListNode*> nodeMap;
RandomListNode *curHead = head;
while (curHead != NULL) {
nodeMap[curHead] = new RandomListNode(curHead->label);
curHead = curHead->next;
}
curHead = head;
while (curHead != NULL) {
nodeMap[curHead]->next = curHead->next != NULL ? nodeMap[curHead->next] : NULL;
nodeMap[curHead]->random = nodeMap[curHead->random];
curHead = curHead->next;
}
return nodeMap[head];
}
};