解决循环链表的方法是什么？

Question

给定一个循环链表,补充一个在循环开始时返回节点的算法.

定义:Cicular链接列表:一个(损坏的)链接列表,其中节点的下一个指针指向较早的节点,以便在链接列表中进行循环.

示例:输入:A-> B-> C-> D-> E-> C [与之前相同的C]输出:C

Answer 1

你可以使用乌龟和野兔algortihm:

1. 从两个指针开始,调用一个tortoise和另一个hare
2. 在每个时间步,将龟推进一次,将野兔推进两次
3. 重复直到它们相等

这为循环内部提供了一个元素.要找到循环的开头:

1. 一步一步地推进乌龟,计算步数
2. 停下来,直到你到达野兔

这将允许您查找循环的长度.然后你只需要步骤size-length时间来找到开始,size"链表"中的元素数量在哪里.

这也称为Floyd的循环检测算法.