为爸妈找飞友 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Reunion - 探亲与陪读

为爸妈找飞友

为爸妈找飞友# Reunion - 探亲与陪读

h*y2012-08-11 07:08

1 楼

suppose that you have a set of nodes with no null pointers (each node points
to itself or to some other node in the set), given a pointer to a node, how
to find the number of different nodes that it ultimately researches by
following links from that node, without modifying any nodes. DO NOT use more
than a constant amount of extra memory space.

b*e2012-08-11 07:08

2 楼

父母8月22号从北京飞华盛顿，有没有同行的，请站内联系，万分感谢！

s*t2012-08-11 07:08

3 楼

use a hash-table to store all the visited node, if a hit happens, stop.
The size of the hash-table is the the number of nodes that it ultimately
can reach.

points
how
more

【在 h*********y 的大作中提到】

: suppose that you have a set of nodes with no null pointers (each node points
: to itself or to some other node in the set), given a pointer to a node, how
: to find the number of different nodes that it ultimately researches by
: following links from that node, without modifying any nodes. DO NOT use more
: than a constant amount of extra memory space.

w*i2012-08-11 07:08

4 楼

我妈9月18号北京飞华盛顿

g*y2012-08-11 07:08

5 楼

each node has only one link? then it's the classic problem of detecting
loop in linklist.

points
how
more

【在 h*********y 的大作中提到】

c*n2012-08-11 07:08

6 楼

I think the key point is how to fix the cycle with out modifying the list.
Any ideas?

【在 g*******y 的大作中提到】

: each node has only one link? then it's the classic problem of detecting
: loop in linklist.
:
: points
: how
: more

a*n2012-08-11 07:08

7 楼

why fix cycle?

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

: I think the key point is how to fix the cycle with out modifying the list.
: Any ideas?

z*e2012-08-11 07:08

8 楼

你们居然看明白这个题？我就没搞懂在说什么，什么叫“that it ultimately
researches by following links from that node”---这是英语？？

points
how
more

【在 h*********y 的大作中提到】

s*t2012-08-11 07:08

9 楼

should be "reach" right? :)

【在 z***e 的大作中提到】

: 你们居然看明白这个题？我就没搞懂在说什么，什么叫“that it ultimately
: researches by following links from that node”---这是英语？？
:
: points
: how
: more

c*n2012-08-11 07:08

10 楼

in other words, how to detect the number of nodes before going to the cycle?

【在 a****n 的大作中提到】

: why fix cycle?

a*n2012-08-11 07:08

11 楼

for single linkedlist, u don't need that number.
1.
get nodes number in cycle = N
2.
for (fastptr = givennode; fastptr < N; fastptr=fastptr->next)
printnode(fastptr);
3.
slowptr = givennode;
do{
printnode(fastptr)
}while (++fastptr != ++slowptr);

cycle?

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

: in other words, how to detect the number of nodes before going to the cycle?

c*n2012-08-11 07:08

12 楼

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~they have the same speed, how to meet?

【在 a****n 的大作中提到】

: for single linkedlist, u don't need that number.
: 1.
: get nodes number in cycle = N
: 2.
: for (fastptr = givennode; fastptr < N; fastptr=fastptr->next)
: printnode(fastptr);
: 3.
: slowptr = givennode;
: do{
: printnode(fastptr)

a*n2012-08-11 07:08

13 楼

cycle length is N

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

:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~they have the same speed, how to meet?

c*n2012-08-11 07:08

14 楼

then?
could you elaborate more?

【在 a****n 的大作中提到】

: cycle length is N

a*n2012-08-11 07:08

15 楼

我说的是单链表
第一个指针先走N步（cycle length is N）。
然后两个指针一起走，第二个指针走到环入口的地方，第一个指针是不是应该走完了
环。
环入口的地方和出口的地方是同一个node吧

c*n2012-08-11 07:08