这道题贴过没有? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

这道题贴过没有?

这道题贴过没有?# Programming - 葵花宝典

N*n2008-07-11 07:07

1 楼

小题一道：
一个链表，每个节点里有俩指针Next和Ranext，各个节点的Next连接起来形成
一个单链表，最后一个节点的Next为NULL。每个节点Ranext指向链内某个节点。
没有任意两个Ranext指向同一个节点。输入这样一个链表，要求在O(N)时间内
复制出一个结构相同的链表。

c*t2008-07-11 07:07

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*n2008-07-11 07:07

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*f2008-07-11 07:07

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 的大作中提到】

c*t2008-07-11 07:07

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*h2008-07-11 07:07

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*f2008-07-11 07:07

7 楼

看了你那个,看起来好像差不多阿,不过你在原链表中interpolation,可以利用判断逻辑
更简单点.
BTW俺这个也是O(1)呀.

写那么多，俺不是给了解么？O (1) space 。
空间

【在 c*****t 的大作中提到】

c*t2008-07-11 07:07

8 楼

你搞错了吧。Nanext 是 side branch，不可能复制所有的 node 。
所以俺说你这有问题。

【在 P*****f 的大作中提到】

: 看了你那个,看起来好像差不多阿,不过你在原链表中interpolation,可以利用判断逻辑
: 更简单点.
: BTW俺这个也是O(1)呀.
:
: 写那么多，俺不是给了解么？O (1) space 。
: 空间

P*f2008-07-11 07:07

9 楼

我不是说乐disjoint cycle么。一次追逐复制一个cycle。然后前进到下一个cycle.
关键是这个"前进到下一个cycle"无需回朔:因为可构造新老指针对在O(1)时间内判断
是否某节点已经复制。
就是说，复制整个Linkedlist得Nanext需要多个循环，但total复杂度仍然是O(n)

你搞错了吧。Nanext 是 side branch，不可能复制所有的 node 。
所以俺说你这有问题。

【在 c*****t 的大作中提到】

:
: 你搞错了吧。Nanext 是 side branch，不可能复制所有的 node 。
: 所以俺说你这有问题。

c*t2008-07-11 07:07

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*f2008-07-11 07:07

11 楼

驽钝了，没得到它...
你贴个伪码吧? heihei

那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
简单？It's SLL...

【在 c*****t 的大作中提到】

: 那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
: 简单？It's SLL...

P*f2008-07-11 07:07

12 楼

大概知道了。的确方便很多，如果把两个链merge在一起。

驽钝了，没得到它...
你贴个伪码吧? heihei
那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
简单？It's SLL...

【在 P*****f 的大作中提到】

: 驽钝了，没得到它...
: 你贴个伪码吧? heihei
:
: 那为什么不直接用 next 复制 node ，然后 update 下 side branch，不更
: 简单？It's SLL...

w*s2008-07-11 07:07

13 楼

side branch updating 很容易。A->Nanext = a->Nanext->next
可以说一下这一段code如何work？不是很了解

w*s2008-07-11 07:07

14 楼

side branch updating 很容易。A->Nanext = a->Nanext->next
可以说一下这一段code如何work？不是很了解

w*s2008-07-11 07:07

15 楼

side branch updating 很容易。A->Nanext = a->Nanext->next
可以说一下这一段code如何work？不是很了解

N*n2008-07-11 07:07

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*m2008-07-11 07:07

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*x2008-07-11 07:07

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) {