C++ Q62: loop in a linked list (Bloomberg) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

C++ Q62: loop in a linked list (Bloomberg)

C++ Q62: loop in a linked list (Bloomberg)# JobHunting - 待字闺中

c*e2010-09-03 07:09

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*w2010-09-03 07:09

2 楼

loop in linked lisk的根本是两个节点的next指向同一个节点，可以作一个hash_map<
Node, reinterpret_castnext()〉, 对linked list 遍历，看有没有
两个next pointer指向同一个Node

h*k2010-09-03 07:09

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 的大作中提到】