b****n 发帖数: 464 | 1 Keep
track
of
two
pointers
in the linked&
#8233; list,
and
start
them
at
the
beginning
of
the
linked
list.
At
each
iteration
of
the
algorithm,
advance
the
first
pointer
by
one
node
and
the
second
pointer by
two
nodes.
If
the
two
pointers
are
ever
the
same
(other
than
at
the
beginning
of
the
algorithm),
then
there &
#8233;is
a
cycle.
If
a
pointer
ever
reaches
the
end
of
the
inked
list
before
the
pointers
are
the
same,
then there
8233;is
no
cycle.
我看到的答案是这样的。但是我觉得不太对啊,比如 node1 指向 node2 指向 node3
指向 node4 指向 node5 指向 node6 指向 node2 |
g**u 发帖数: 504 | 2 they will meet at node 6.
linked&
8233;
8233;
&
【在 b****n 的大作中提到】 : Keep
track
of
two
pointers
in the linked& : #8233; list,
and
start
them
at
the
: beginning
of
the
linked
list. :
At
each
iteration
of
the
: algorithm,
advance
the
first
pointer
by : one
node
and
the
second
pointer by
: two
nodes. :
If
the
two
pointers
are
: ever
the
same
(other
than
at
the : beginning
of
the
algorithm),
then
there &
|
b****n 发帖数: 464 | 3 为什么呢?
第1步: pointer 1 at node 1; pointer 2 at node 1;
第2步: pointer 1 at node 2; pointer 2 at node 3;
第3步: pointer 1 at node 3; pointer 2 at node 5;
第4步: pointer 1 at node 4; pointer 2 at node 2; (结束)
还是说,至此不算结束,还继续?
第5步: pointer 1 at node 5; pointer 2 at node 4;
第6步: pointer 1 at node 6; pointer 2 at node 6;
答案其实还有一句,就是说pointer 2不一定要只跳一格,可以每次跳n (n>1)格,
那么,是不是说,根据圈的大小,有时候要绕比较多圈,两个pointer才刚好遇得上?
而且,反正有圈,两个pointer如果遇不上,就会一直转下去? |
z*********8 发帖数: 2070 | 4 这当然不算结束
n->next == NULL 才算结束, 有环的情况永远不会结束,直到相遇
【在 b****n 的大作中提到】 : 为什么呢? : 第1步: pointer 1 at node 1; pointer 2 at node 1; : 第2步: pointer 1 at node 2; pointer 2 at node 3; : 第3步: pointer 1 at node 3; pointer 2 at node 5; : 第4步: pointer 1 at node 4; pointer 2 at node 2; (结束) : 还是说,至此不算结束,还继续? : 第5步: pointer 1 at node 5; pointer 2 at node 4; : 第6步: pointer 1 at node 6; pointer 2 at node 6; : 答案其实还有一句,就是说pointer 2不一定要只跳一格,可以每次跳n (n>1)格, : 那么,是不是说,根据圈的大小,有时候要绕比较多圈,两个pointer才刚好遇得上?
|