algorithm - 在没有弗洛伊德循环检测算法的情况下检测链表中的循环

Question

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

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

例如。

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

这里的2->next和3->next是一样的，都是4的地址，也就是说链表中有环，4是环节点。而从4遍历到4就得到了循环中的节点数。

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

Answer 1

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