删除单链表中的循环

Question

循环可以出现在单链表(SLL)中.
要删除列表中的循环,首先我们需要检测SLL中的循环,然后删除循环.

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

Answer 1

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

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