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，我们需要保存原结点对应的新结点来完成deep copy。时间复杂度为O(n), 空间复杂度为O(n)。
class Solution { public: RandomListNode *copyRandomList(RandomListNode *head) { if(head == NULL) return NULL; unordered_map<RandomListNode *, RandomListNode *> pmap; for(RandomListNode *p = head; p; p = p->next){ RandomListNode * q = new RandomListNode(p->label); pmap[p] = q; } for(RandomListNode *p = head; p; p = p->next){ if(p->next) pmap[p]->next = pmap[p->next]; if(p->random) pmap[p]->random = pmap[p->random]; } return pmap[head]; } };
Leetcode: Copy List with Random Pointer
原文：http://www.cnblogs.com/Kai-Xing/p/4121771.html