链表循环检测算法

Question

我看了一些面试问题,在网上关于你如何发现是否有一个链表一环,和解决方案(Floyd的循环查找算法)是有两个指针,一个是比其他快2倍,并检查他们再次相遇.

我的问题是:为什么我不能只保持一个指针固定,只是每次将另一个指针向前移动1步？

Answer 1

因为可能不是完整的linkedList在循环内.

对于链表套索检测算法,您需要两个指针:

只要第一个指针是牛仔所在的位置,就不会检测到循环.但如果你逐步向前移动它,它最终会进入循环.

顺便说一句,套索是图论的终点技术,牛仔不是.

Answer 2

因为第一个(非移动)指针可能不在循环内,所以指针永远不会相遇.(请记住,循环可能只包含列表的一部分.)

Answer 3

因为循环可能不包含第一个指针指向的元素.

例如,如果第一个指针指向元素1并且链接列表稍后有一个循环(1-> 2-> 3-> 4-> 2),则您的算法将不会检测到它.