s*w 发帖数: 729 | 1 一时没想起来最佳做法,用了个笨点的办法
第一个循环:用原表的 next 指针,copy 节点到新表,同时存两个表各自的 index 到
node* 的对应
第二个循环:用原表的 random 指针,建立第一个表里 index 到 index 的对应
第三个循环:用前两个循环的结果更新新表
30分钟写完,调了10分钟,期间一个compiler error, 两个 run time error (
vector忘记用push_back 直接[]了,一个变量写错),一个错误(新表尾部加新node忘
记更新尾指针),然后就 ac 了,难道现在没 lte 了? |
b**********5 发帖数: 7881 | 2 这题很简单啊, 和那个deepcopy graph的题, 不是一模一样么? |
s*w 发帖数: 729 | 3 还没做 graph clone, 刚开始做新题
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题很简单啊, 和那个deepcopy graph的题, 不是一模一样么?
|
f******n 发帖数: 198 | 4 第一步建copy的时候把原来node的next指向copy,然后把copy的next指向原来的next,
等于把两个链表zip起来,这样就不用额外的空间建index了。 |
T******e 发帖数: 157 | 5 lz如何实现index Node*的? 每次都遍历array去找对应的pointer吗? |
s*w 发帖数: 729 | 6 map addr2ind; // 原表
vector ind2addr; // 新表
vector ind2ind; // 原表里的 random 链接
新表不用每个node都遍历搜索当前的 random 指针,直接取; 都对应存好了
【在 T******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : lz如何实现index Node*的? 每次都遍历array去找对应的pointer吗?
|
b**********5 发帖数: 7881 | 7 贴个我做的
public RandomListNode copyRandomList(RandomListNode head) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
HashMap m = new HashMap<
RandomListNode, RandomListNode>();
RandomListNode result = null;
RandomListNode prev = null;
while (head != null) {
RandomListNode headCopy; RandomListNode randomCopy;
if (m.containsKey(head)) {
headCopy = m.get(head);
}
else {
headCopy = new RandomListNode(head.label);
m.put(head, headCopy);
}
if (head.random != null) {
if (m.containsKey(head.random)) {
randomCopy = m.get(head.random);
}
else {
randomCopy = new RandomListNode(head.random.label);
m.put(head.random, randomCopy);
}
headCopy.random = randomCopy;
}
if (prev==null) {
result = headCopy;
}
else {
prev.next = headCopy;
}
prev = headCopy;
head = head.next;
}
return result;
}
【在 s*w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : map addr2ind; // 原表 : vector ind2addr; // 新表 : vector ind2ind; // 原表里的 random 链接 : 新表不用每个node都遍历搜索当前的 random 指针,直接取; 都对应存好了
|
s*w 发帖数: 729 | 8 这个想法真别致;我看过的,几天没温习就全忘记了;你一讲,我又想明白了大部分,
多谢
1. 每个 node 完整(我的只有value)copy construct
2. interleave 复制的 node
3. 把所有复制 node 的 random 改成原node random指针指向 node 的 next
4. 改每个 node 的 next 到下一个
5. 返回第二个 node
太考脑筋了,怕过几天又忘记了
【在 f******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一步建copy的时候把原来node的next指向copy,然后把copy的next指向原来的next, : 等于把两个链表zip起来,这样就不用额外的空间建index了。
|
s*w 发帖数: 729 | 9 不熟悉 Java, 看起来比较费劲,我再琢磨下
reused
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 贴个我做的 : public RandomListNode copyRandomList(RandomListNode head) { : // Note: The Solution object is instantiated only once and is reused : by each test case. : HashMap m = new HashMap< : RandomListNode, RandomListNode>(); : RandomListNode result = null; : RandomListNode prev = null; : while (head != null) { : RandomListNode headCopy; RandomListNode randomCopy;
|
c********p 发帖数: 1969 | 10 你的prev干嘛用的?
为什么要纪录pre?
reused
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 贴个我做的 : public RandomListNode copyRandomList(RandomListNode head) { : // Note: The Solution object is instantiated only once and is reused : by each test case. : HashMap m = new HashMap< : RandomListNode, RandomListNode>(); : RandomListNode result = null; : RandomListNode prev = null; : while (head != null) { : RandomListNode headCopy; RandomListNode randomCopy;
|
s********u 发帖数: 1109 | 11 感觉你们的想法都太tricky了,我想不到。我就是存两个map,一个新节点对应到旧节
点,另一个旧节点对应到新节点。。。
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
unordered_map< RandomListNode *, RandomListNode *> oldNew;
unordered_map< RandomListNode *, RandomListNode *> newOld;
RandomListNode *runner = head;
RandomListNode *dummy = new RandomListNode(0);
RandomListNode *curr = dummy;
while(runner){
curr->next = new RandomListNode(runner->label);
oldNew[runner] = curr->next;
newOld[curr->next] = runner;
runner = runner->next;
curr = curr->next;
}
curr = dummy->next;
while(curr){
RandomListNode *old = newOld[curr];
if(old->random )
curr->random = oldNew[old->random];
curr = curr->next;
}
return dummy->next;
}
}; |
p****U 发帖数: 109 | 12 RandomListNode *copyRandomList(RandomListNode *head) {
// Note: The Solution object is instantiated only once and is reused by
each test case.
//first parse
if(!head)
return NULL;
RandomListNode *cur=head;
while(cur){
RandomListNode *tmp=cur->next;
cur->next=new RandomListNode(cur->label);
cur=cur->next;
cur->next=tmp;
cur=cur->next;
}
//second parse
cur=head;
RandomListNode *copy;
while(cur){
copy=cur->next;
if(cur->random)
copy->random=cur->random->next;
cur=cur->next->next;
}
//third parse
cur=head;
RandomListNode *copyHead=head->next;
while(cur){
RandomListNode *copy=cur->next;
cur->next=cur->next->next;
if(!cur->next)
break;
copy->next=copy->next->next;
cur=cur->next;
}
return copyHead;
}
我也调了一会,其实就是打错一个next指针。 |