首页 > 代码库 > Copy List with Random Pointer （Hash表）
Copy List with Random Pointer （Hash表）
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.
class Solution {public: RandomListNode *copyRandomList(RandomListNode *head) { if(head==NULL) return head; map<RandomListNode*,int> hash; map<int,RandomListNode*> copyHash; RandomListNode* copyHead=new RandomListNode(head->label); RandomListNode* p=head; RandomListNode* q=copyHead; int index=0; hash[p]=index; copyHash[index]=q; ++index; p=p->next; //复制整个链表 while(p!=NULL){ RandomListNode* newNode=new RandomListNode(p->label); q->next=newNode; q=q->next; hash[p]=index; copyHash[index]=q; ++index; p=p->next; } //最后的NULL节点也要加进去 hash[NULL]=index; copyHash[index]=NULL; //复制random指针 int i=0; RandomListNode* r=head; while (i<hash.size()&&r!=NULL) { copyHash[i]->random=copyHash[hash[r->random]]; ++i; r=r->next; } return copyHead; }};
Copy List with Random Pointer （Hash表）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。