首页 > 代码库 > [leetcode] Copy List with Random Pointer
[leetcode] Copy List with Random Pointer
Copy List with Random Pointer
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的节点。看了别人的做法，豁然开朗。unordered_map存储的是本链表的某个节点和复制之后的链表对应的节点，即链表的第二个节点对应复制链表的第二个节点（深度复制，那当然两个节点一样）。第一步完成之后，链表的next域全部复制完成，同时节点也对应起来了。第二步，假设p1与p2为对应的节点，那么p1->random节点也会对应p2->random，所以又map[p1]->random = map[p1->random]。
题解：
/** * 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) { if(head==NULL) return NULL; unordered_map<RandomListNode*, RandomListNode*> map; RandomListNode *head2 = new RandomListNode(head->label); RandomListNode *p1 = head, *p2 = head2; map[p1] = p2; p1 = p1->next; while(p1) { RandomListNode *tmp = new RandomListNode(p1->label); map[p1] = tmp; p2->next = tmp; p2 = tmp; p1 = p1->next; } p1 = head; while(p1) { if(p1->random) map[p1]->random = map[p1->random]; p1 = p1->next; } return head2; }};
后话：
还是参考了一篇博客。上面的方法空间复杂度为O(n)，还有一种O(1)的方法，感觉太牛逼了，看看就好，第一种方法要吃透，哈希表存储的新旧两个对应的节点很值得学习。
/** * 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) { if(head==NULL) return head; RandomListNode *pos1 = head, *pos2 = head->next; while(pos1!=NULL) { pos1->next = new RandomListNode(pos1->label); pos1->next->next = pos2; pos1 = pos2; if(pos2!=NULL) pos2 = pos2->next; } pos1 = head; pos2 = head->next; while(pos1!=NULL) { if(pos1->random==NULL) pos2->random==NULL; else pos2->random = pos1->random->next; pos1 = pos2->next; if(pos2->next!=NULL) pos2 = pos2->next->next; } RandomListNode *res = head->next; pos1 = head; pos2 = res; while(pos2->next!=NULL) { pos1->next = pos2->next; pos1 = pos2->next; pos2->next = pos1->next; pos2 = pos1->next; } pos1->next = NULL; pos2->next = NULL; return res; }};
[leetcode] Copy List with Random Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。