确定单链表是否有循环是一个常见的面试问题。但是为什么会存在一个带有循环的链表呢？带循环的链表什么时候有用？
问问题
205 次
5 回答
4
如果您想从随机迭代器开始迭代整个列表或在任何位置插入，循环链接列表可能很有用。它们简化了这些操作的算法，因为您不必考虑列表的开头或结尾。
于 2012-08-10T13:39:41.120 回答
1
例如，将哪些元素作为参数传递给函数并不重要。使用哨兵模式时，您将相同地遍历每个元素。
于 2012-08-10T13:35:21.743 回答
0
Apache 使用循环链表来存储它的所有过滤器。
出于某种原因，他们给它起了一个花哨的营销名称（“Bucket Brigades”），并称之为“一项重大创新” ——哈哈。
于 2012-08-10T15:48:54.417 回答
0
要使用循环链表，您可以考虑本质上是循环的结构。例如按 FIFO 顺序使用和释放的缓冲区池，或应按循环顺序分时共享的一组进程，或按特定顺序保存多边形的节点坐标。
于 2012-08-16T11:23:43.610 回答
0
这里给出的许多答案都考虑了完全循环的链表。
面试问题有点不同。我们必须在链接的某处检测循环（可以是部分的）
例如：（对不起，糟糕的图形）
1 -> 2 -> 3 -> 4 -> 5
^ v
7 <----- 6
回答它如何发生：链接损坏。
a) 试图通过 UGC（用户生成内容）入侵的人。可能会出现不良数据。
b) 早期阶段的设计缺陷。
这种循环检测也是我们在 LinkedLists 上进行的测试的一部分，以寻找可疑的错误。
您没有要求解决方案，但我将在这里简要介绍一些：
- 继续将节点推送到 List（Java 中的 Arraylist）。发现重复的时间：检测到循环
- 海龟和野兔方法。Turtle 一次跳过一个节点。兔子，一次两个。如果这是一个循环，他们会相遇
- 遍历时存储布尔标志 *visited*。*true* 的任何遭遇都是循环。
于 2012-11-22T05:58:17.250 回答