首页 > 代码库 > Copy List with Random Pointer （16）
Copy List with Random Pointer （16）
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.
要复制一个链表，但是要做到深度复制，如果每个链表节点中只有一个next指针的话会很容易，直接从前往后复制就行了。但是这个神奇的链表节点中有random pointer，如果采取从前往后复制的方法，可能random pointer对应的节点还没有生成，这时无法进行赋值了。可以采取这种策略，利用map key-value对 的性质，先将新生成的链表结点的random pointer指向老结点中的random pointer值。每生成一个新节点，就把新老节点的对应key-value对 存入map。等新链表的主体部分生成完毕，再利用map将新链表结点中的random pointer指向新生成的结点。
思路很简单，实现也比较容易，直接上代码了！
1 /** 2 * Definition for singly-linked list with a random pointer. 3 * struct RandomListNode { 4 * int label; 5 * RandomListNode *next, *random; 6 * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 RandomListNode *copyRandomList(RandomListNode *head) {12 if(!head)13 return NULL;14 unordered_map<RandomListNode *,RandomListNode * > map;15 RandomListNode *tmp=NULL;16 RandomListNode *h;17 while(head){18 if(tmp==NULL){19 tmp=new RandomListNode(head->label);20 tmp->random=head->random;21 h=tmp;22 }23 else{24 tmp->next=new RandomListNode(head->label);25 tmp=tmp->next;26 tmp->random=head->random;27 }28 map.insert(pair<RandomListNode *,RandomListNode *>(head,tmp));29 head=head->next;30 }31 tmp=h;32 while(tmp){33 tmp->random=map[tmp->random];34 tmp=tmp->next;35 }36 return h;37 }38 };
Copy List with Random Pointer （16）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。