h*********y 发帖数: 49 | 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. |
s***t 发帖数: 49 | 2 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.
|
g*******y 发帖数: 1930 | 3 each node has only one link? then it's the classic problem of detecting
loop in linklist.
points
how
more
【在 h*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.
|
c*********n 发帖数: 1057 | 4 I think the key point is how to fix the cycle with out modifying the list.
Any ideas?
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : each node has only one link? then it's the classic problem of detecting : loop in linklist. : : points : how : more
|
a****n 发帖数: 1887 | 5 why fix cycle?
【在 c*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I think the key point is how to fix the cycle with out modifying the list. : Any ideas?
|
z***e 发帖数: 5393 | 6 你们居然看明白这个题?我就没搞懂在说什么,什么叫“that it ultimately
researches by following links from that node”---这是英语??
points
how
more
【在 h*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.
|
s***t 发帖数: 49 | 7 should be "reach" right? :)
【在 z***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你们居然看明白这个题?我就没搞懂在说什么,什么叫“that it ultimately : researches by following links from that node”---这是英语?? : : points : how : more
|
c*********n 发帖数: 1057 | 8 in other words, how to detect the number of nodes before going to the cycle?
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : why fix cycle?
|
a****n 发帖数: 1887 | 9 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : in other words, how to detect the number of nodes before going to the cycle?
|
c*********n 发帖数: 1057 | 10
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~they have the same speed, how to meet?
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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****n 发帖数: 1887 | 11 cycle length is N
【在 c*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~they have the same speed, how to meet?
|
c*********n 发帖数: 1057 | 12 then?
could you elaborate more?
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : cycle length is N
|
a****n 发帖数: 1887 | 13 我说的是单链表
第一个指针先走N步(cycle length is N)。
然后两个指针一起走, 第二个指针走到环入口的地方, 第一个指针是不是应该走完了
环。
环入口的地方和出口的地方是同一个node吧 |
c*********n 发帖数: 1057 | 14 啊。。。恍然大悟,谢谢
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我说的是单链表 : 第一个指针先走N步(cycle length is N)。 : 然后两个指针一起走, 第二个指针走到环入口的地方, 第一个指针是不是应该走完了 : 环。 : 环入口的地方和出口的地方是同一个node吧
|
h*********y 发帖数: 49 | 15 呵呵,typo,typo
大家都做题做多了,灵犀一点通阿,呵呵
【在 s***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : should be "reach" right? :)
|
h*********y 发帖数: 49 | 16 不好意思问句,怎么找出N来?
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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)
|
c*********n 发帖数: 1057 | 17 1. 2个pointer一起走,一个快一个慢,直到相遇,然后记下这个点
2. 循环一次直到再次走到这个点
【在 h*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不好意思问句,怎么找出N来?
|
h*********y 发帖数: 49 | 18 恍然大悟,
谢谢
谢谢
【在 c*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. 2个pointer一起走,一个快一个慢,直到相遇,然后记下这个点 : 2. 循环一次直到再次走到这个点
|