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

Question

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

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

EG。

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

这里2->下和3->下是一样的，这是地址4.这意味着链表中有一个循环，4是循环节点。并且从4到4的遍历将给出循环中的节点的数量。

有没有办法让我们继续这个方法？

Answer 1

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