无Floyds循环检测算法的链表循环检测

Question

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

在这个场景中，两个节点的地址将指向同一个节点(循环节点)。

例如：

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

这里2->next和3->next是相同的，它是4的地址。这意味着在链表中有一个循环，而4是循环节点。从4到4的遍历将给出循环中的节点数。

我们有什么办法可以这样做吗？

Answer 1

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