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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 你们居然看明白这个题？我就没搞懂在说什么，什么叫“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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~they have the same speed, how to meet?
|
c*********n
发帖数: 1057 | 12 then?
could you elaborate more?
【在 a****n 的大作中提到】
: cycle length is N
|
a****n
发帖数: 1887 | 13 我说的是单链表
第一个指针先走N步（cycle length is N）。
然后两个指针一起走， 第二个指针走到环入口的地方， 第一个指针是不是应该走完了
环。
环入口的地方和出口的地方是同一个node吧 |
c*********n
发帖数: 1057 | 14 啊。。。恍然大悟，谢谢
【在 a****n 的大作中提到】
: 我说的是单链表
: 第一个指针先走N步（cycle length is N）。
: 然后两个指针一起走， 第二个指针走到环入口的地方， 第一个指针是不是应该走完了
: 环。
: 环入口的地方和出口的地方是同一个node吧
|
h*********y
发帖数: 49 | 15 呵呵,typo,typo
大家都做题做多了，灵犀一点通阿，呵呵
【在 s***t 的大作中提到】
: should be "reach" right? :)
|
h*********y
发帖数: 49 | 16 不好意思问句，怎么找出N来？
【在 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)
|
c*********n
发帖数: 1057 | 17 1. 2个pointer一起走，一个快一个慢，直到相遇，然后记下这个点
2. 循环一次直到再次走到这个点
【在 h*********y 的大作中提到】
: 不好意思问句，怎么找出N来？
|
h*********y
发帖数: 49 | 18 恍然大悟，
谢谢
谢谢
【在 c*********n 的大作中提到】
: 1. 2个pointer一起走，一个快一个慢，直到相遇，然后记下这个点
: 2. 循环一次直到再次走到这个点
|
