use*_*754 4 algorithm linked-list circular-list
我是一个更新鲜的人,我在最近的一次采访中被问到了这个问题.
问题是--- 通过遍历链表的每个元素只需查看单个链表是否在任何点都是循环的.
对此我回答说,我们将在遍历另一个链表中的列表时存储每个节点的引用,并且对于正在测试的列表中的每个节点,我们将查找列表中是否存在引用存储引用.
采访者说他需要一种更优化的方法来解决这个问题.
任何人都可以告诉我什么是更优化的方法来解决这个问题.
PS:在任何一点我都是圆形的,我的意思是这个.http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg
面试官正在寻找你是否知道一个官方称为Floyd's cycle-finding algorithm或Tortoise and hare非正式的技巧.
这个想法是在一个循环中推进两个指针,一个每次迭代移动两次,另一个只移动一次.如果快速移动的指针从后面赶上缓慢移动的指针,则列表有一个循环.
该算法检测O(n)时间和O(1)存储周期."慢"指针通过列表不超过一次,因此可以说算法在单次遍历中找到答案.
在我看来,这个算法提出了一个糟糕的面试问题,因为除非你事先知道,否则现场有点难以提出.与此同时,这不是一个广泛使用的算法,每个人都必须知道它,让我想知道为什么有人会在采访中询问它.
