algorithm - 在没有 Floyds 循环检测算法的情况下检测链表中的循环

Question

在一次采访中，我被要求检测链表中的循环节点并计算循环中的节点数。由于我不知道 flyod 算法，我试图找出自己的方法。

这个想法是在这种情况下，两个节点的地址将指向同一个节点（循环节点）。

例如。

1-->2-->4-->5-->7-->3-->4

这里 2->next 和 3->next 是一样的，都是 4 的地址。也就是说链表中有一个循环，4 是循环节点。并且从 4 遍历到 4 将给出循环中的节点数。

有没有办法我们可以继续使用这种方法？？？？

Answer 1

当然，您可以通过维护一组已经访问过的地址来轻松找到一个循环。由于您对循环大小感兴趣，因此您可以将其设为地图：address->count. 计数是在访问相应地址的节点时访问了多少节点。当您发现表中已经存在一个节点时，您可以通过从当前值中减去表中的计数来获得循环大小。当然，您可以通过维护“已访问”位并在节点本身中计数来获得相同的效果。然后不需要单独的地图。