突击刷题： copy a linked list with random pointer

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/** * 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: /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ RandomListNode *copyRandomList(RandomListNode *head) { // write your code here if (!head) return 0; unordered_map<RandomListNode*, RandomListNode*> map; RandomListNode* root=head; while(root){ map[root]=new RandomListNode(root->label); root=root->next; } root=head; while(root){ if (root->next) map[root]->next=map[root->next]; if (root->random) map[root]->random=map[root->random]; root=root->next; } return map[head]; } };