c***2
发帖数: 838 | 1 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续） |
s*******e
发帖数: 93 | 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就是这样 |
c***2
发帖数: 838 | 3 very good idea.
1) First pass: duplicate each node
2) Second pass: populate new other pointers
3) Third pass: split the list
Thanks! |
h**********d
发帖数: 4313 | |
