copy link with random additional pointers# JobHunting - 待字闺中
c*2
1 楼
复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
s*e
2 楼
I saw this problem earlier here. The answer is:
(imagine you have a->b->c->d, lets call the other pointer as "other"
1. duplicate each node and insert after itself. Now you get a->a->b->b->c->c->d->d
2. node n=head
while(n!=null)
n->next->other = n->other->next
n=n->next->next
3. separate the two lists
head2 = head->next
node n=head
while(n->next->next !=null)
n->next->next = n->next->next->next
n->next = n->next->next
n=n->next
n->next = null
n->next->next = null
不知道implement有没有错，不过idea就是这样
(imagine you have a->b->c->d, lets call the other pointer as "other"
1. duplicate each node and insert after itself. Now you get a->a->b->b->c->c->d->d
2. node n=head
while(n!=null)
n->next->other = n->other->next
n=n->next->next
3. separate the two lists
head2 = head->next
node n=head
while(n->next->next !=null)
n->next->next = n->next->next->next
n->next = n->next->next
n=n->next
n->next = null
n->next->next = null
不知道implement有没有错，不过idea就是这样
c*2
3 楼
very good idea.
1) First pass: duplicate each node
2) Second pass: populate new other pointers
3) Third pass: split the list
Thanks!
1) First pass: duplicate each node
2) Second pass: populate new other pointers
3) Third pass: split the list
Thanks!
h*d
4 楼
相关阅读
请教 BI data analyst的career path是不是所有中国人都希望 壮大 中国人的队伍啊？？明天M家二合一onsite求教，签了offer之后可以反悔么？2个master的opt问题请问：Google onsite 之后A家电面面试官是technique recruiter会是什么情况呢这个recruiter是怎么回事？Junior software developer openning有人有像我一样倒霉吗？公司的犯罪背景调查怎么还调查我在中国的档案？报offer，顺便问怎么negotiate找工作还是从了老板找的一个postdoc？ (转载)export control license疑问贴个自己的答案：Binary Tree Max Path SumAmazon这算啥情况呀green card holder still need export license?Background check 是在正式offer前还是后？这最小公共父母节点有bug吗？求问:我该继续读书，还是去找工作？