3

リンクされたリストでサイクルを検出するための私のコードは次のとおりです。

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. このコードを簡素化/美化する他の方法はありますか?

4

4 に答える 4

2

ループ内のコードの重複を取り除く方法はありますか?

どうですか：

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

 tortoise = tortoise.next();

それは決して大幅な改善ではありません。

カメを一歩前に出させた後は、チェックは必要ないと思いますか?

はい、あなたが正しく推論したように、カメはウサギが動く直前に常にウサギの後ろにいます。そのため、カメは以前に覆われた地面を常に覆っています。

レース中に何らかの理由でデータ構造が変更された場合、もちろんこれは当てはまりません (ただし、そうであれば、はるかに大きな問題が発生することになります)。

このコードを簡素化/美化する他の方法はありますか?

私が考えることができるわけではありません。

于 2011-03-17T16:03:46.053 に答える
1

これは、Steve のコメントに基づいて改善されたコードです (バック センチネル ノードがそれ自体にリンクされています)。

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

これによりクライアント コードが壊れる場所は見当たらず、ユニット テストでそれが確認されました。偉大な ：）

于 2011-03-17T16:33:25.480 に答える
1

単一の if ステートメントを使用して、||短絡演算子であるという事実を使用できます。これはもう少し簡潔ですが、理解しにくい可能性があり、コードの重複がまだあります。

    do
    {
        if ((hare = hare.next()) == back || 
            (hare = hare.next()) == back) 
                return;            
        tortoise = tortoise.next();
    }
    while (tortoise != hare);
于 2011-03-17T16:38:38.613 に答える
0

for (int i = 0; i < 2; i++)重複を避けるために、ループを使用できます。それ以外は、そこにある最も単純なコードをほとんど手に入れたと思います。

于 2011-03-17T16:05:06.140 に答える