首页 > 其他 > 详细

LeetCode | Copy List with Random Pointer

时间:2014-04-15 12:41:50      阅读:459      评论:0      收藏:0      [点我收藏+]

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.

Shallow copy:

Some members of the copy may reference the same objects as the original.

Deep copy:

All members of the original are cloned. There are no shared objects.

主要区别在于拷贝之后指针成员指向的是不是同一个地址。

这道题最naive的方法就是用一个unordered_map来存original pointer和copied pointer的对应关系。空间复杂度o(n),时间复杂度o(n)。

bubuko.com,布布扣
 1 class Solution {
 2 public:
 3     RandomListNode *copyRandomList(RandomListNode *head) {
 4         if (head == NULL) return NULL;
 5         unordered_map<RandomListNode*, RandomListNode*> pointerMap;
 6         
 7         RandomListNode *p = head, *copyH = NULL, *copyT = NULL, *tmp;
 8         while (p != NULL) {
 9             tmp = new RandomListNode(p->label);
10             tmp->random = p->random;
11             if (copyH == NULL) {
12                 copyH = tmp;
13             } else {
14                 copyT->next = tmp;
15             }
16             copyT = tmp;
17             pointerMap[p] = tmp;
18             p = p->next;
19         }
20         
21         p = copyH;
22         
23         while (p != NULL) {
24             p->random = pointerMap[p->random];
25             p = p->next;
26         }
27         
28         return copyH;
29     }
30 };
bubuko.com,布布扣

比较smart的方法是,将copied node放在对应的original node后面,也就是original node1->copied node1->original node2->copied node2->....

然后就可以用p->random->next来求得random的新地址了。 

最后再把copied list和original list分离开。

以后如果有题目需要把两个list对应起来的话,可以采用相同的方式,把它们串起来。

bubuko.com,布布扣
 1 RandomListNode *copyRandomList(RandomListNode *head) {
 2     if(head == NULL) return NULL;
 3     RandomListNode *p = head;
 4     do {
 5         RandomListNode *q = p->next;
 6         p->next = new RandomListNode(p->label);
 7         p->next->next = q;
 8         p = q;
 9     } while(p != NULL);
10     p = head;
11     do {
12         p->next->random = (p->random == NULL) ? NULL : p->random->next;
13         p = p->next->next;
14     } while(p != NULL);
15     p = head;
16     RandomListNode *r = head->next;
17     for(RandomListNode *q = r;;) {
18         p->next = q->next;
19         p = p->next;
20         if(p == NULL) break;
21         q->next = p->next;
22         q = q->next;
23     }
24     return r;
25 }
bubuko.com,布布扣

LeetCode | Copy List with Random Pointer,布布扣,bubuko.com

LeetCode | Copy List with Random Pointer

原文:http://www.cnblogs.com/linyx/p/3664037.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!