15

リンクリストでサイクルを検出するために、2つのポインター（遅いポインターと速いポインター）を保持するHareandTortoiseアプローチを使用できることを理解しています。ただし、wikiやその他のリソースを読んだ後、2つのポインターがO（n）時間計算量で一致することが保証されている理由がわかりません。

4

4 に答える 4

33

これが非公式の証明の試みです。

サイクルの形は関係ありません。尾が長く、最後に向かってループすることも、尾のない最初から最後までループすることもできます。サイクルの形に関係なく、1つ明らかなことがあります。それは、亀のポインターがウサギのポインターに追いつかないということです。二人が出会ったことがあったら、うさぎのポインターは後ろから亀のポインターに追いつく必要があります。

それが確立されたら、2つの可能性を検討してください。

  1. うさぎのポインターは亀のポインターの一歩後ろにあります。
  2. うさぎのポインターは亀のポインターの2歩後ろにあります。

それ以上の距離はすべて、最終的に1つまたは2つに減少します。

亀のポインターが常に最初に移動すると仮定すると（逆の場合もあります）、最初のケースでは、亀のポインターが1歩進みます。これで、それらの間の距離は2になります。うさぎのポインタが2ステップ進むと、同じノードに着地します。理解を容易にするために、同じものを示しています。テキストが多すぎると邪魔になる可能性があります。

♛=うさぎ
♙=カメ
X=両方が会う

..♛♙...＃1-最初は、うさぎは亀の一歩後ろにあります。
..♛.♙..＃2-これで亀は一歩踏み出しました。今、うさぎは2歩遅れています。
.... X ..＃3-次に、うさぎは2つのステップを踏み、彼らは出会います！

次に、それらの間の距離が2である2番目のケースを考えてみましょう。遅いポインターが1ステップ前進し、それらの間の距離が3になります。次に、速いポインターが2ステップ前進し、それらの間の距離が1に減少します。彼らがもう1つのステップで会うことをすでに証明した最初のケ​​ース。繰り返しますが、理解しやすいように図解されています。

.♛.♙...＃1-最初、うさぎは亀の2歩後ろにあります。
.♛..♙..＃2-これで亀は1歩進み、3歩離れます。
...♛♙..＃3-次に、うさぎは前の場合と同じ2つのステップを実行します。

ここで、このアルゴリズムがO（n）にあることが保証されている理由については、ウサギが先に進む前にカメに出会うことをすでに確立しているものを使用してください。つまり、両方がループ内に入ると、亀が次のラウンドを完了する前に、ウサギが2倍の速さで移動するため、ウサギと出会うことになります。最悪の場合、ループはn個のノードを持つ円になります。亀はnステップで1ラウンドしか完了できませんが、ウサギはその間に2ラウンドを完了できます。ノウサギが最初のラウンドでカメを逃したとしても（そうなるでしょう）、それは間違いなく2番目のラウンドでカメに追いつくでしょう。

于 2011-06-26T08:53:44.783 に答える
3

イテレータAをB使用して、リストをそれぞれ1つと2つずつ調べます。ループが存在することを考慮してください。Aそして、ループに入った瞬間、Bすでにその中のどこかにあります。ループの長さが、の場合、K移動でループのB周りを走ります]K/2[。したがって、多くの場合、反復で、距離またはの後ろに表示され、それが'番目のターン2*]K/2[になる状況が発生します。この後、明らかに、彼らはで会うか、移動します。したがって、ループが存在し、ある位置で開始する場合、最大で反復を実行します。BA1: B->A2: B->.->AB12P2*P + 2*]K/2[ + 2 = O(N)

于 2011-06-26T08:58:04.993 に答える
0

これは、カメとウサギのアルゴリズムのwhileループです。

    while tortoise:
        hare = hare.next
        tortoise = tortoise.next
        # if not hare, states that i have a single node.
        # hare.next means that we have a tail value. So we do not have a cycle
        if (not hare) or (not hare.next):
            return False
        else:
            hare = hare.next
        if tortoise == hare:
            return True

うさぎは2歩前進しますが、これはサイクル内で何度もループし、複数のノードに何度も何度も触れる可能性があることを意味します。技術的に言えば、すべてが1つのwhileループ内で発生します。

于 2021-11-03T00:11:48.473 に答える
-1 
//if you just want to check if there is a loop

loop = false;
item = head-of-list; 
while (item != nil)
{
   if (item.next < 0) 
   {
      loop = true; 
      break; 
   }
   else
   {
      actual = item;
      item = item.next; 
      actual.next = actual.next * -1; 
   }
} 

return loop;
于 2013-08-19T15:58:47.927 に答える