首页 > 代码库 > Copy List with Random Pointer
Copy List with Random Pointer
这个题目是深度复制链表，就是所有节点都是新分配的空间，这一点不难做到，难的是新链表random指针的赋值，想想也没什么好办法，就用map存储两个链表的映射关系，在第一次遍历时只新建节点，建立链表，令新链表中节点的random值等于旧链表的值。第二次遍历再根据map一一映射。
1 class Solution { 2 public: 3 RandomListNode *copyRandomList(RandomListNode *head) { 4 if(head == NULL) 5 return NULL; 6 RandomListNode* nHead = new RandomListNode(head->label); 7 RandomListNode* optr; 8 RandomListNode* nptr; 9 optr = head;10 nptr = nHead;11 map<RandomListNode*,RandomListNode*> m1;12 m1[optr] = nptr;13 nptr->random = optr->random;14 optr = optr->next;15 while(optr != NULL)16 {17 RandomListNode* tmp = new RandomListNode(optr->label);18 nptr->next = tmp;19 nptr = tmp;20 nptr->random = optr->random;21 m1[optr]=nptr;22 optr = optr->next;23 24 }25 nptr->next = NULL;26 nptr = nHead;27 while(nptr != NULL)28 {29 if(nptr->random != NULL)30 {31 nptr->random = m1[nptr->random];32 }33 nptr = nptr->next;34 }35 return nHead;36 }37 };
Copy List with Random Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。