y***n
发帖数: 6764 | | s*****g
发帖数: 3 | 2 set p as the starting point, then
go through the linked list and check whether current point is eq p.
stop until you get back to p or you get to the end of the list.
am I right? | r*********r
发帖数: 3195 | 3 i got asked this question in my phone interview, which i got it right:
color all the nodes white first,
then each node you visit, color it black,
when you see a node whose "next" field is a black node,
you got a circle.
there is a follow-up question to this one, which is harder. :) | p*u
发帖数: 2454 | 4 要是node不能碰你怎么办，傻眼了？？
【在 r*********r 的大作中提到】
: i got asked this question in my phone interview, which i got it right:
: color all the nodes white first,
: then each node you visit, color it black,
: when you see a node whose "next" field is a black node,
: you got a circle.
: there is a follow-up question to this one, which is harder. :)
| r*********r
发帖数: 3195 | 5 那就另用一个hash table, 作指针到颜色的映射。
不过这个的内存开销是线性的。
所以原题的标准答案还是一快一慢两个指针的龟兔算法。
如果没见过答案的话，很怀疑谁能在电话上想出来。
我答的是用 bloom filter, 这样内存开销可以减小，
但是可能有false positive。
interviewer 也就没有纠缠下去。 |
|
