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.
复制一个带有随机后续节点的链表,
因为随机后续节点可能在复制到当前结点时还没有被创建出来,所以需要保存新节点和老节点之间的对应关系。
当然也有人通过在老节点后插入新节点的方法完成,这样的好处是空间复杂度降低了,但坏处是实现起来麻烦一些,而且如果链表中有环,这样的方法将失效。
/**
* 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) {
unordered_map <RandomListNode*, RandomListNode*> mp;
if(!head) return NULL;
RandomListNode* p = head;
RandomListNode* res = new RandomListNode(head->label);
RandomListNode* q = res;
mp[p] = q;
while(p->next)
{
p = p->next;
q->next = new RandomListNode(p->label);
q = q->next;
mp[p] = q;
}
p = head;
q = res;
while(p)
{
q->random = mp[p->random];
p = p->next;
q = q->next;
}
return res;
}
};