algorithm - 我的龟兔赛跑可以改进吗？

Question

这是我用于检测链表中循环的代码：

do
{
    hare = hare.next();
    if (hare == back) return;

    hare = hare.next();
    if (hare == back) return;

    tortoise = tortoise.next();
}
while (tortoise != hare);
throw new AssertionError("cyclic linkage");

1. 有没有办法摆脱循环内的代码重复？

2. 我是否正确地假设在使乌龟向前迈出一步后我不需要检查？在我看来，乌龟永远不会在兔子之前到达列表的末尾（与寓言相反）。

3. 还有其他方法可以简化/美化此代码吗？

Answer 1

有没有办法摆脱循环内的代码重复？

怎么样：

for(int i = 0; i < 2; i++)
{
    hare = hare.next();
    if (hare == back) return;
}

 tortoise = tortoise.next();

无论如何，这都不是一个巨大的改进。

我是否正确地假设在使乌龟向前迈出一步后我不需要检查？

是的，正如您正确推理的那样，乌龟总是在兔子移动之前就在兔子后面。所以乌龟总是覆盖以前覆盖过的地面。

如果数据结构在比赛期间因任何原因发生了变异，这当然不再正确（但如果是这样，您将遇到更大的问题）。

还有其他方法可以简化/美化此代码吗？

不是我能想到的。

Answer 2

这是我根据史蒂夫的评论改进的代码（将后哨节点链接到自身）：

while (hare != back)
{
    tortoise = tortoise.next();
    hare = hare.next().next();
    if (hare == tortoise) throw new AssertionError("cyclic linkage");
}

我看不到任何会破坏客户端代码的地方，我的单元测试证实了这一点。伟大的 ：）

Answer 3

||您可以使用单个 if 语句并使用短路运算符这一事实。这有点简洁，但可能更难理解，并且仍然存在代码重复。

    do
    {
        if ((hare = hare.next()) == back || 
            (hare = hare.next()) == back) 
                return;            
        tortoise = tortoise.next();
    }
    while (tortoise != hare);

Answer 4

为避免重复，您可以使用for (int i = 0; i < 2; i++)循环。除此之外，我认为您几乎已经获得了最简单的代码。