最近在一次求职面试中，我被要求开发一种可以确定链表是否循环的算法。因为它是一个链表，我们不知道它的大小。它是一个双向链表，每个节点都有“下一个”和“上一个”指针。一个节点可以连接到任何其他节点，也可以连接到自身。
当时我想到的唯一解决方案是选择一个节点并将其与链表的所有节点进行检查。面试官显然不喜欢这个想法，因为它不是最佳解决方案。什么是更好的方法？
最佳答案
您正在寻找的是循环查找算法。 Joel 提到的算法被称为“龟兔赛跑”算法或 Floyd 的循环查找算法。我更喜欢第二种，因为它听起来像是一个很好的 D&D 咒语。
关于c++ - 循环链表算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3151276/