如何使用额外的指针打印链表中的所有周期？

How to print all cycles in a linked list with extra pointers?

提问人：shivam agarwal 提问时间：10/28/2020 最后编辑：trentshivam agarwal 更新时间：10/28/2020 访问量：111

问：

给定一个类似于链表的数据结构，其中指针指向下一个节点，另一个指针指向任何随机节点，我必须打印该结构具有的所有唯一循环。下面是此数据结构的示例：

enter image description here

这里的唯一循环是 （1,2,1）、（2,3,4,5,2）、（1,3,5,2,1）、（3,4,3） 等，但 （1,2,3,4,5,2,1）、（1,2,3,4,3） 不是循环。 打印所有这些独特循环的算法应该是什么？

数据结构 与语言无关 图论 循环检测

评论

0赞 Guy Coder 10/29/2020
把它想象成一个图表，你可能是因为你标记了它，并使用了 Tarjan 的强连接组件算法graph-theory
0赞 trent 10/29/2020
@GuyCoder 实际上，是我添加了图论，但我不认为 Tarjan 的算法可以解决问题。图中的图形只有一个 SCC（整个图形），但问题是如何找到简单的循环。
0赞 Guy Coder 10/29/2020
@trentcl谢谢。现在它看起来很有趣，可以尝试解决，但不是今天，明天可能。

答： 暂无答案

上一个：为什么抽象数据类型只能由具体数据类型实现？

下一个：二叉搜索树的最小值不能是最左边的条目吗？