N********n
发帖数: 8363 | 1 小题一道：
一个链表，每个节点里有俩指针Next和Ranext，各个节点的Next连接起来形成
一个单链表，最后一个节点的Next为NULL。每个节点Ranext指向链内某个节点。
没有任意两个Ranext指向同一个节点。输入这样一个链表，要求在O(N)时间内
复制出一个结构相同的链表。 |
c*****t
发帖数: 1879 | 2 If can modify the original list (and then restore it back), can be
done in the following way I think:
original: a-b-c-d
new: a-A-b-B-c-C-d-D
Then can update the side branches. Then restore back.
【在 N********n 的大作中提到】
: 小题一道：
: 一个链表，每个节点里有俩指针Next和Ranext，各个节点的Next连接起来形成
: 一个单链表，最后一个节点的Next为NULL。每个节点Ranext指向链内某个节点。
: 没有任意两个Ranext指向同一个节点。输入这样一个链表，要求在O(N)时间内
: 复制出一个结构相同的链表。
|
N********n
发帖数: 8363 | 3 Modification is allowed.
【在 c*****t 的大作中提到】
: If can modify the original list (and then restore it back), can be
: done in the following way I think:
: original: a-b-c-d
: new: a-A-b-B-c-C-d-D
: Then can update the side branches. Then restore back.
|
P*****f
发帖数: 2272 | 4 我的思路
观察: 追逐Ranext 指针,可将老链表partition为多个disjoint cycles.
算法:
1.建立新链表时,第一次大循环pass只复制Nanext结构.
1.1 对老链表指针追逐,for current disjoint cycle
1.1.1 分配新链表对应节点,复制内容，并设置新链表节点相互之间的Nanext.
1.1.2 注意到此时
a) 老链表已经discovered得cycle节点其Nanext指针信息已复制到新链表中
,属于冗余,可利用为in-pace 空间
b) 其新链表对应的节点next指针不包含有效信息,可利用为in-place空间
for-each 新老节点对 in current cycle（老/新位置的对应有其在cycle
中的相对位置决定）做如下指针操作--为了将来在新链表中复制next结构:
1.1.2.1 老节点的Nanext指向新节点;
1.1.2.2 新节点的next指向老节点。
1.2 forward sca
【在 N********n 的大作中提到】
: 小题一道：
: 一个链表，每个节点里有俩指针Next和Ranext，各个节点的Next连接起来形成
: 一个单链表，最后一个节点的Next为NULL。每个节点Ranext指向链内某个节点。
: 没有任意两个Ranext指向同一个节点。输入这样一个链表，要求在O(N)时间内
: 复制出一个结构相同的链表。
|
c*****t
发帖数: 1879 | 5 写那么多，俺不是给了解么？O (1) space 。
a-A-b-B-c-C-d-D
(caps are new nodes).
side branch updating 很容易。A->Nanext = a->Nanext->next
所以俺就没提。
这道题要是按照正规的 serialization 办法解（O (n) space）就没意思了。
空间
【在 P*****f 的大作中提到】
: 我的思路
: 观察: 追逐Ranext 指针,可将老链表partition为多个disjoint cycles.
: 算法:
: 1.建立新链表时,第一次大循环pass只复制Nanext结构.
: 1.1 对老链表指针追逐,for current disjoint cycle
: 1.1.1 分配新链表对应节点,复制内容，并设置新链表节点相互之间的Nanext.
: 1.1.2 注意到此时
: a) 老链表已经discovered得cycle节点其Nanext指针信息已复制到新链表中
: ,属于冗余,可利用为in-pace 空间
: b) 其新链表对应的节点next指针不包含有效信息,可利用为in-place空间
|
i***h
发帖数: 12655 | 6 椰子大师对我贴的那个Cormen二叉树遍历的习题有解没有? 谢谢
【在 c*****t 的大作中提到】
: 写那么多，俺不是给了解么？O (1) space 。
: a-A-b-B-c-C-d-D
: (caps are new nodes).
: side branch updating 很容易。A->Nanext = a->Nanext->next
: 所以俺就没提。
: 这道题要是按照正规的 serialization 办法解（O (n) space）就没意思了。
:
: 空间
|
P*****f
发帖数: 2272 | 7 看了你那个,看起来好像差不多阿,不过你在原链表中interpolation,可以利用判断逻辑
更简单点.
BTW俺这个也是O(1)呀.
写那么多，俺不是给了解么？O (1) space 。
空间
【在 c*****t 的大作中提到】
: 写那么多，俺不是给了解么？O (1) space 。
: a-A-b-B-c-C-d-D
: (caps are new nodes).
: side branch updating 很容易。A->Nanext = a->Nanext->next
: 所以俺就没提。
: 这道题要是按照正规的 serialization 办法解（O (n) space）就没意思了。
:
: 空间
|
c*****t
发帖数: 1879 | 8
你搞错了吧。Nanext 是 side branch，不可能复制所有的 node 。
所以俺说你这有问题。
【在 P*****f 的大作中提到】
: 看了你那个,看起来好像差不多阿,不过你在原链表中interpolation,可以利用判断逻辑
: 更简单点.
: BTW俺这个也是O(1)呀.
:
: 写那么多，俺不是给了解么？O (1) space 。
: 空间
|
P*****f
发帖数: 2272 | 9 我不是说乐disjoint cycle么。一次追逐复制一个cycle。然后前进到下一个cycle.
关键是这个"前进到下一个cycle"无需回朔:因为可构造新老指针对在O(1)时间内判断
是否某节点已经复制。
就是说，复制整个Linkedlist得Nanext需要多个循环，但total复杂度仍然是O(n)
你搞错了吧。Nanext 是 side branch，不可能复制所有的 node 。
所以俺说你这有问题。
【在 c*****t 的大作中提到】
:
: 你搞错了吧。Nanext 是 side branch，不可能复制所有的 node 。
: 所以俺说你这有问题。
|
c*****t
发帖数: 1879 | 10 那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
简单？It's SLL...
【在 P*****f 的大作中提到】
: 我不是说乐disjoint cycle么。一次追逐复制一个cycle。然后前进到下一个cycle.
: 关键是这个"前进到下一个cycle"无需回朔:因为可构造新老指针对在O(1)时间内判断
: 是否某节点已经复制。
: 就是说，复制整个Linkedlist得Nanext需要多个循环，但total复杂度仍然是O(n)
:
: 你搞错了吧。Nanext 是 side branch，不可能复制所有的 node 。
: 所以俺说你这有问题。
|
|
|
P*****f
发帖数: 2272 | 11 驽钝了，没得到它...
你贴个伪码吧? heihei
那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
简单？It's SLL...
【在 c*****t 的大作中提到】
: 那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
: 简单？It's SLL...
|
P*****f
发帖数: 2272 | 12 大概知道了。的确方便很多，如果把两个链merge在一起。
驽钝了，没得到它...
你贴个伪码吧? heihei
那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
简单？It's SLL...
【在 P*****f 的大作中提到】
: 驽钝了，没得到它...
: 你贴个伪码吧? heihei
:
: 那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
: 简单？It's SLL...
|
w*********s
发帖数: 6 | 13 side branch updating 很容易。A->Nanext = a->Nanext->next
可以说一下这一段code如何work？ 不是很了解 |
w*********s
发帖数: 6 | 14 side branch updating 很容易。A->Nanext = a->Nanext->next
可以说一下这一段code如何work？ 不是很了解 |
w*********s
发帖数: 6 | 15 side branch updating 很容易。A->Nanext = a->Nanext->next
可以说一下这一段code如何work？ 不是很了解 |
N********n
发帖数: 8363 | 16
roughly like this:
Node duplicate (Node original) {
Node old, clone, cloneHead;
if (original == null)
return null;
old = original;
while (old != null) {
clone = new Node ();
clone.nx = old.ranx;
old.ranx = clone;
old = old.nx
} // hook clone up with old
old = original;
while (old != null) {
clone = old.ranx;
clone.ranx = clone.ranx.ranx;
old = old.nx;
} // set clone.ranx
old = original;
cloneHead = old.ranx;
while (old.nx != null)
【在 w*********s 的大作中提到】
: side branch updating 很容易。A->Nanext = a->Nanext->next
: 可以说一下这一段code如何work？ 不是很了解
|
r******m
发帖数: 6 | 17 大师，讲讲这个“正规的 serialization 办法”？
谢谢啊
发信人: coconut (向唐僧大师学习中), 信区: Programming
标 题: Re: 这道题贴过没有?
发信站: BBS 未名空间站 (Fri Jul 11 14:10:56 2008), 站内
写那么多，俺不是给了解么？O (1) space 。
a-A-b-B-c-C-d-D
(caps are new nodes).
side branch updating 很容易。A->Nanext = a->Nanext->next
所以俺就没提。
这道题要是按照正规的 serialization 办法解（O (n) space）就没意思了。 |
p****x
发帖数: 707 | 18 clone.ranx = clone.ranx.ranx;
where clone.ranx.ranx point to? thanks
【在 N********n 的大作中提到】
:
: roughly like this:
: Node duplicate (Node original) {
: Node old, clone, cloneHead;
:
: if (original == null)
: return null;
:
: old = original;
: while (old != null) {
|
