Может ли быть улучшена моя раса черепаха против зайца?

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

Вы можете использовать один оператор if и использовать тот факт, что || является оператором короткого замыкания.Это немного более кратко, но может быть труднее понять, и все еще есть дублирование кода.

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

Answer 3

Вот мой улучшенный код, основанный на комментарии Стива (имеющий ссылку на обратный дозорный узел):

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

Я не вижу места, где это могло бы нарушить код клиента, и мои модульные тестыподтвердите это.Отлично :) 1004 *

Answer 4

Чтобы избежать дублирования, вы можете использовать цикл for (int i = 0; i < 2; i++).Кроме этого, я думаю, что у вас есть самый простой код, который вы можете иметь прямо здесь.