Wykrywanie cykli na liście połączonej z metodą Hare i Tortoise

Question

Rozumiem, że w celu wykrycia cyklu na liście połączonej mogę użyć podejścia Hare i Tortoise, które zawiera 2 wskaźniki (wolne i szybkie). Jednak po przeczytaniu w wiki i innych zasobach, nie rozumiem, dlaczego jest zagwarantowane, że te dwa wskaźniki spotkają się w złożoności czasu O (n).

Answer 1

Oto próba nieformalnego dowodu.

Kształt cyklu nie ma znaczenia. Może mieć długi ogon i pętlę pod koniec, lub tylko pętlę od początku do końca bez ogona. Niezależnie od kształtu cyklu jedno jest jasne - że wskaźnik żółwia nie może dogonić wskaźnika zająca. Jeśli obaj mieli się kiedykolwiek spotkać, wskaźnik zająca musi odciąć wskaźnik żółwia od tyłu.

Mając to ustalone, należy rozważyć dwa realnych możliwościach:

1. zając wskaźnik jest o jeden krok za wskaźnik żółwia.
2. Wskaźnik zająca znajduje się dwa kroki za wskaźnikiem żółwia.

Wszystkie większe odległości zostaną ostatecznie zredukowane do jednego lub dwóch.

Zakładając, że wskaźnik żółwia zawsze porusza się pierwszy (może być na odwrót), to w pierwszym przypadku wskaźnik żółwia robi krok do przodu. Teraz odległość między nimi wynosi 2. Kiedy wskaźnik zajścia ma teraz 2 kroki, trafią one do tego samego węzła. Oto ta sama ilustracja, dla łatwiejszego zrozumienia. Zbyt dużo tekstu może przeszkadzać.

 
♛ = hare 
♙ = tortoise 
X = both meet 

..♛♙... #1 - Initially, the hare is one step behind the tortoise. 
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind. 
....X.. #3 - Next, the hare takes two steps and they meet! 

Rozważmy teraz drugi przypadek, w którym odległość między nimi wynosi 2. powolny wskaźnik przesuwa się o jeden krok do przodu, a odległość między nimi staje 3. Następnie szybko wskaźnik porusza się do przodu i dwa kroki, odległość między nimi zmniejsza się do 1, który jest identyczny z pierwszym przypadkiem, w którym już udowodniliśmy, że spotkają się w jeszcze jednym kroku. Ponownie, zilustrowane dla łatwiejszego zrozumienia.

 
.♛.♙... #1 - Initially, the hare is two steps behind the tortoise. 
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart. 
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case. 

Teraz, dlaczego ten algorytm jest gwarancją w O (n), wykorzystać to, co mamy już ustalone, że zając będzie spotkać żółwia zanim idzie naprzód. Oznacza to, że gdy obie znajdują się w pętli, zanim żółw zakończy kolejną rundę, spotka się z zająca, ponieważ zając porusza się dwa razy szybciej. W najgorszym przypadku pętla będzie kołem o n węzłach. Podczas gdy żółw może ukończyć tylko jedną rundę w n krokach, zając może ukończyć dwie rundy w tym czasie. Nawet jeśli zająca tęsknił za żółwiem w pierwszej rundzie (co zrobi), to w drugiej rundzie zdecydowanie dogoni żółwia.

Answer 2

Niech iteratory A i B przechodzą przez listę odpowiednio przez nich i przez dwa. Bardziej istnieje pętla. Wtedy, gdy A wejdzie w pętlę, B będzie już gdzieś w środku. Jeśli długość pętli jest K, następnie B będzie biegać to w ]K/2[ ruchów, więc co najwyżej 2*]K/2[ iteracji będziemy mieli sytuację, gdy B pojawia się za A w odległości 1: B->A lub 2: B->.->A, a to B „th kolei. Potem oczywiście spotkamy się w ruchach 1 lub . Jeśli więc pętla istnieje i zaczyna się w jakiejś pozycji P, wykonujemy co najwyżej 2*P + 2*]K/2[ + 2 = O(N) iteracje.

Answer 3

//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;