s*w
发帖数: 729 | 1 一时没想起来最佳做法，用了个笨点的办法
第一个循环：用原表的 next 指针，copy 节点到新表，同时存两个表各自的 index 到
node* 的对应
第二个循环：用原表的 random 指针，建立第一个表里 index 到 index 的对应
第三个循环：用前两个循环的结果更新新表
30分钟写完，调了１０分钟，期间一个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 的大作中提到】
: 这题很简单啊， 和那个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 的大作中提到】
: 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 的大作中提到】
: map addr2ind; // 原表
: vector ind2addr; // 新表
: vector ind2ind; // 原表里的 random 链接
: 新表不用每个node都遍历搜索当前的 random 指针，直接取; 都对应存好了
|
s*w
发帖数: 729 | 8 这个想法真别致；我看过的，几天没温习就全忘记了；你一讲，我又想明白了大部分，
多谢
１. 每个 node 完整（我的只有value）copy construct
2. interleave 复制的 node
３. 把所有复制 node 的 random 改成原node random指针指向 node 的 next
4. 改每个 node 的 next 到下一个
５. 返回第二个 node
太考脑筋了，怕过几天又忘记了
【在 f******n 的大作中提到】
: 第一步建copy的时候把原来node的next指向copy，然后把copy的next指向原来的next，
: 等于把两个链表zip起来，这样就不用额外的空间建index了。
|
s*w
发帖数: 729 | 9 不熟悉 Java， 看起来比较费劲，我再琢磨下
reused
【在 b**********5 的大作中提到】
: 贴个我做的
: 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 的大作中提到】
: 贴个我做的
: 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指针。 |
