algorithm - 删除单链表中的循环

Question

单链表 (SLL) 中可能会出现循环。
要删除列表中的循环，首先我们需要检测 SLL 中的循环，然后删除循环。

谁能告诉如何用伪代码删除 SLL 中的循环？
我们可以使用 3 个指针吗？
有没有替代品来完成任务？

Answer 1

您提出的问题有很多解决方案。最简单但效率低的方法之一是反转列表，同时记住头节点。如果你回到头节点，那么你就知道存在一个循环。

另一种检查方法是为列表中的每个节点创建一个包含一个 int 的数组，每次访问一个节点时，增加其在数组中的对应值。然后您所要做的就是检查数组中的值是否超过一个，然后将其与额外迭代开始的位置进行比较。此方法检测完整循环和小循环。希望这会有所帮助。