c**********e
发帖数: 2007 | 1 Find whether there is a loop in a linked list. Do you have other ways
instead of using a quick pointer and a slow pointer?
The problem was discussed, but no solution is found. Anybody has an idea?
Original source:
http://www.mitbbs.com/article_t/JobHunting/31529203.html | f**********w
发帖数: 93 | 2 loop in linked lisk的根本是两个节点的next指向同一个节点，可以作一个hash_map<
Node, reinterpret_castnext()〉, 对linked list 遍历，看有没有
两个next pointer指向同一个Node | h**k
发帖数: 3368 | 3 你这个算法需要O(n)的additional storage.
详细讨论见http://ostermiller.org/find_loop_singly_linked_list.html和http://en.wikipedia.org/wiki/Cycle_detection
这个问题还要注意另外两个扩展，在知道有loop后，如何找到loop的起点和长度；或者
如何证明你的算法是对的。
map<
【在 f**********w 的大作中提到】
: loop in linked lisk的根本是两个节点的next指向同一个节点，可以作一个hash_map<
: Node, reinterpret_castnext()〉, 对linked list 遍历，看有没有
: 两个next pointer指向同一个Node
|
|
