Wyjaśnij, jak działa wyszukiwanie węzła początkowego cyklu na liście połączonej z cyklem?

Rozumiem, że spotkanie Żółwia i Zająca kończy istnienie pętli, ale w jaki sposób przeniesienie żółwia na początek połączonej listy przy jednoczesnym utrzymaniu zająca w miejscu spotkania, a następnie przesuwanie obu krok po kroku sprawia, że ​​spotykają się w punkcie początkowym cyklu?

To jest algorytm Floyda do wykrywania cykli . Pytasz o drugą fazę algorytmu - po znalezieniu węzła będącego częścią cyklu, jak znaleźć początek cyklu?

W pierwszej części algorytmu Floyda zając porusza się o dwa kroki na każdy krok żółwia. Jeśli żółw i zając kiedykolwiek się spotkają, istnieje cykl, a miejsce spotkania jest częścią cyklu, ale niekoniecznie pierwszym węzłem w cyklu.

Kiedy żółw i zając spotykają się, znaleźliśmy najmniejsze i (liczbę kroków podjętych przez żółwia) takie, że X _i = X _2i . Niech mi reprezentuje liczbę kroków do przejścia od X ₀ do początku cyklu, a lambda niech reprezentuje długość cyklu. Wtedy i = mu + a lambda, i 2i = mu + b lambda, gdzie a i b są liczbami całkowitymi oznaczającymi, ile razy żółw i zając przeszli przez cykl. Odejmowanie pierwszego równania od drugiego daje i = (ba) * lambda, więc i jest całkowitą wielokrotnością lambda. Dlatego X _{i + mu} = X _mu . X _i reprezentuje miejsce spotkania żółwia i zająca. Jeśli przesuniesz żółwia z powrotem do węzła początkowego X₀ , i pozwól żółwiowi i zającowi kontynuować z tą samą prędkością, po dodatkowych krokach żółw osiągnie X _mu , a zając osiągnie X _{i + mu} = X _mu , więc drugie miejsce spotkania oznacza początek cykl.

Spróbuję wyjaśnić własnymi słowami algorytm wykrywania cykli, który znajduje się pod adresem http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare .

Jak to działa

Niech żółw i zając (nazwa wskaźników) wskazują na początek listy cyklem, jak na powyższym schemacie.

Postawmy hipotezę, że jeśli przesuniemy żółwia o 1 krok na raz i zając o 2 kroki na raz, w końcu spotkają się w pewnym momencie. Pokażmy, że przede wszystkim ta hipoteza jest prawdziwa.

Rysunek przedstawia listę z cyklem. Cykl ma długość ni początkowo moddalamy się od niego o kilka kroków. Powiedzmy również, że miejsce spotkania jest kkilka kroków od początku cyklu, a żółw i zając spotykają się, gdy żółw zrobi icałkowite kroki. (Hare podjąłby wtedy 2itotalne kroki).

Muszą być spełnione następujące 2 warunki:

1) i = m + p * n + k

2) 2i = m + q * n + k

Pierwsza mówi, że żółw porusza się po ikrokach iw tych ikrokach najpierw dostaje się do cyklu. Następnie przechodzi przez pczasy cyklu dla pewnej liczby dodatniej p. W końcu przechodzi przez kkolejne węzły, aż napotka zająca.

Podobnie jest z zającem. Porusza się 2ikrokami iw tych 2ikrokach najpierw dostaje się do cyklu. Następnie przechodzi przez qczasy cyklu dla pewnej liczby dodatniej q. W końcu przechodzi przez kwięcej węzłów, aż napotka żółwia.

Ponieważ zając podróżuje z podwójną prędkością żółwia, a czas jest stały dla obu, kiedy docierają do miejsca spotkania.

Używając prostej zależności prędkości, czasu i odległości,

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

Spośród m, n, k, p, q, pierwsze dwie są właściwościami podanej listy. Jeśli potrafimy wykazać, że istnieje co najmniej jeden zbiór wartości k, q, p, który sprawia, że ​​to równanie jest prawdziwe, to pokażemy, że hipoteza jest poprawna.

Jeden taki zestaw rozwiązań wygląda następująco:

p = 0

q = m

k = m n - m

Możemy sprawdzić, czy te wartości działają w następujący sposób:

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

W tym zestawie ijest

i = m + p n + k

=> m + 0 * n + mn - m = mn.

Oczywiście powinieneś zobaczyć, że niekoniecznie jest to najmniejsze możliwe. Innymi słowy, żółw i zając mogły się już spotkać wiele razy. Ponieważ jednak pokazujemy, że spotykają się one przynajmniej raz, możemy powiedzieć, że hipoteza jest poprawna. Więc musieliby się spotkać, gdybyśmy przesunęli jeden z nich o 1 stopień, a drugi o 2 stopnie naraz.

Teraz możemy przejść do drugiej części algorytmu, czyli znaleźć początek cyklu.

Początek cyklu

Gdy żółw i zając spotkają się, umieśćmy żółwia z powrotem na początku listy i trzymajmy zająca w miejscu, w którym się spotkali (czyli o k kroków od początku cyklu).

Hipoteza jest taka, że ​​jeśli pozwolimy im poruszać się z tą samą prędkością (1 krok dla obu), pierwszy raz spotkają się ponownie, będzie to początek cyklu.

Udowodnijmy tę hipotezę.

Załóżmy najpierw, że jakaś wyrocznia mówi nam, czym jest m.

Następnie, jeśli pozwolimy im poruszać się m + k kroków, żółw musiałby dotrzeć do punktu, w którym pierwotnie się spotkali (k kroków od początku cyklu - patrz rysunek).

Wcześniej to pokazaliśmy m + k = (q - 2p) n.

Ponieważ m + k kroków jest wielokrotnością długości cyklu n, zając w międzyczasie przeszedłby cykl (q-2p) razy i wróciłby do tego samego punktu (k kroków od początku cyklu).

Teraz, zamiast pozwolić im poruszać się m + k kroków, jeśli pozwolimy im poruszać się tylko m kroków, żółw przybyłby na początek cyklu. Zającowi brakłoby k kroków do wykonania obrotów (q-2p). Ponieważ zaczynał k kroków przed początkiem cyklu, zając musiałby dojść do początku cyklu.

W rezultacie wyjaśnia to, że musieliby spotkać się na początku cyklu po pewnej liczbie kroków po raz pierwszy (za pierwszym razem, ponieważ żółw właśnie przybył do cyklu po m krokach i nigdy nie widział zająca, który był już w cykl).

Teraz wiemy, że liczba kroków, które musimy przesunąć, aż się spotkają, okazuje się być odległością od początku listy do początku cyklu, m. Oczywiście algorytm nie musi wiedzieć, czym jest m. Po prostu poruszy zarówno żółwia, jak i zająca, krok po kroku, aż się spotkają. Punktem spotkania musi być początek cyklu, a liczba kroków musi być odległością (m) do początku cyklu. Zakładając, że znamy długość listy, możemy również obliczyć długość cyklu odejmowania m od długości listy.

Zobacz ten obraz:

Odległość przebyta przez slowPointer przed spotkaniem = x + y

Odległość przebyta przez fastPointer przed spotkaniem = (x + y + z) + y = x + 2y + z

Ponieważ fastPointer porusza się z dwukrotnie większą prędkością niż slowPointer, a czas jest stały dla obu, gdy dotrze do miejsca spotkania.

Czyli używając prostej zależności prędkości, czasu i odległości 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z

W związku z tym, przesuwając slowPointer na początek połączonej listy i sprawiając, że zarówno slowPointer, jak i fastPointer przenoszą jeden węzeł na raz, oba mają tę samą odległość do pokonania .

Dotrą do punktu, w którym zaczyna się pętla na połączonej liście.

_{Prosta i niedoceniana odpowiedź Old Monka wyjaśnia znalezienie cyklu, gdy szybki biegacz wykonuje tylko jeden pełny cykl. W tej odpowiedzi wyjaśniam przypadek, w którym szybki biegacz wykonał pętlę wiele razy, zanim powolny biegacz wejdzie w pętlę.}

Używając tego samego obrazu:

Powiedzmy, że szybki biegacz pokonał pętlę m razy przed spotkaniem wolnego i szybkiego. To znaczy że:

• Dystans pokonany wolno: x + y
• Dystans pokonany szybko: x + m (y + z) + y, czyli dodatkowe y w miejscu ich spotkania

Ponieważ szybkie biegi z dwukrotnie większą prędkością niż wolne i że biegły one w tym samym czasie, oznacza to, że jeśli podwoimy dystans pokonany przez wolne, otrzymamy dystans pokonany szybko. A zatem,

• 2 (x + y) = x + m (y + z) + y

Rozwiązywanie dla x daje,

x = (m - 1) (y + z) + z

W prawdziwym scenariuszu oznaczałoby to, x = (m - 1) cała pętla + dodatkowy dystans z .

Stąd, jeśli umieścimy jeden wskaźnik na początku listy, a drugi zostawimy w miejscu spotkania, to przesunięcie ich z tą samą prędkością spowoduje, że wskaźnik w pętli ukończy m - 1 przebiegów pętli, a następnie napotka drugi wskaźnik bezpośrednio na początku pętli.

To bardzo proste. Możesz myśleć w kategoriach prędkości względnej. Jeśli królik porusza się o dwa węzły, a żółw przesuwa się o jeden węzeł, w stosunku do żółwia, królik porusza się o jeden węzeł (załóżmy, że żółw odpoczywa). Tak więc, jeśli przesuniemy jeden węzeł na liście połączonej cyklicznie, z pewnością spotkamy się ponownie w tym miejscu.

Po znalezieniu punktu połączenia wewnątrz listy połączonej kołowo problem sprowadza się teraz do znalezienia punktu przecięcia dwóch połączonych list.

W czasie pierwszego zderzenia żółw wykonał m + k kroków, jak pokazano powyżej. Zając porusza się dwa razy szybciej niż żółw, co oznacza, że ​​zając wykonał 2 (m + k) kroki. Z tych prostych faktów możemy wyprowadzić następujący wykres.

W tym momencie przenosimy żółwia z powrotem na początek i deklarujemy, że zarówno zając, jak i żółw muszą poruszać się o jeden krok na raz. Z definicji, po m krokach, żółw będzie na początku cyklu. Gdzie będzie zając?

Zając również będzie na początku cyklu. Wynika to jasno z drugiego wykresu: kiedy żółw cofnął się do początku, zając przeszedł k kroków do ostatniego cyklu. Po m krokach zając zakończy kolejny cykl i zderzy się z żółwiem.

Podejście:

Istnieją dwie wskazówki:

• Powolny wskaźnik, który porusza jeden węzeł na raz.
• Szybki wskaźnik, który przesuwa jednocześnie dwa węzły.

Jeśli te dwa wskaźniki spotykają się, oznacza to, że istnieje pętla. Gdy się spotkają, jeden z węzłów wskaże głowę, a następnie oba węzły przejdą do jednego węzła na raz. Spotkają się na początku pętli.

Uzasadnienie: Gdzie spotykają się, kiedy dwoje ludzi idzie okrężnym torem, jeden z nich z dwukrotnie większą prędkością od drugiego? Dokładnie tam, gdzie zaczęli.

Teraz załóżmy, że szybki biegacz ma przewagę na starcie kkroków na nokrążeniu krokowym. gdzie się spotkają Dokładnie po n-kkrokach. Gdy biegacz wolny pokonywałby (n-k)kroki, biegacz szybki pokrywałby k+2(n-k)kroki. ( tj. k+2n-2kkroki, czyli 2n-kkroki ). tj. (n-k)kroki (ścieżka jest okrężna i nie interesuje nas liczba rund, po których się spotykają; interesuje nas tylko pozycja, w której się spotykają).

W jaki sposób szybki biegacz uzyskał przewagę na początku kkroków? Ponieważ powolnemu biegaczowi zajęło tyle kroków, aby dotrzeć do początku pętli. Zatem początek pętli to k kroków od węzła głównego.

Uwaga: Węzeł, w którym spotkały się oba wskaźniki, jest koddalony o kilka kroków od początku pętli (wewnątrz pętli), a węzeł główny jest koddalony o kilka kroków od początku pętli. Więc kiedy wskaźnik przesuwa się w równym tempie 1 kroku od bota, te węzły spotkają się na początku pętli.

Uważam, że jest to proste. Daj mi znać, jeśli jakaś część jest niejednoznaczna.

Okej, załóżmy więc, że zając i żółw spotykają się w punkcie oddalonym o k kroków od początku cyklu, liczba kroków przed rozpoczęciem cyklu wynosi mi, a długość cyklu to L.

Więc teraz w miejscu spotkania ->

Odległość pokonana przez żółwia = mu + a * L + k - Równanie 1

(Kroki podjęte w celu osiągnięcia początku cyklu + kroki podjęte w celu pokrycia iteracji `` a '' cyklu + k kroków od początku cyklu) (gdzie a jest pewną dodatnią stałą)

Odległość pokonana przez zająca = mu + b * L + k - Równanie 2

(Kroki podjęte w celu osiągnięcia początku cyklu + kroki podjęte w celu pokrycia iteracji `` b '' cyklu + k kroków od początku cyklu) (gdzie b jest pewną dodatnią stałą, a b> = a)

Zatem dodatkowa odległość pokonana przez zająca to = Równanie 2 - Równanie 1 = (ba) * L

Należy pamiętać, że ta odległość jest również równa odległości żółwia od punktu wyjścia, ponieważ zając porusza się 2 razy szybciej niż żółw. Można to przyrównać do „mu + k”, które jest również odległością miejsca spotkania od początku, jeśli nie uwzględnimy wielu przejść cyklu.

Zatem mu + k = (ba) * L

Zatem mi kroki od tego punktu prowadziłyby z powrotem do początku cyklu (ponieważ k kroków od początku cyklu zostało już zrobionych, aby dotrzeć do punktu spotkania). Może się to zdarzyć w tym samym cyklu lub w dowolnym z kolejnych cykli. Tak więc, jeśli teraz przeniesiemy żółwia na początek połączonej listy, zajmie to kilka kroków, aby dotrzeć do punktu początkowego cyklu, a zając zrobi wiele kroków, aby również dotrzeć do początku cyklu, a zatem obaj spotkają się na punkt początkowy cyklu.

PS Szczerze mówiąc, miałem w głowie to samo pytanie, co oryginalny plakat i przeczytałem pierwszą odpowiedź, wyjaśnili kilka rzeczy, ale nie mogłem jasno dojść do końcowego wyniku, więc starałem się zrobić to po swojemu i łatwiej było to zrozumieć.

kredyt obrazu

Odległość wywołania liczba łączy, po których podąża wskaźnik, oraz czas, przez ile iteracji algorytm przesuwa powolny wskaźnik o jedno łącze, a szybki wskaźnik o dwa łącza. Istnieje N węzłów przed cyklem o długości C, oznaczonych jako przesunięcie cyklu od k = 0 do C-1.

Aby dotrzeć do początku cyklu, zwolnienie zajmuje N czasu i odległości. Oznacza to, że szybkie zajmuje N dystansu w cyklu (N aby się tam dostać, N aby obrócić). Tak więc w czasie N, powolny jest przy przesunięciu cyklu k = 0, a szybki przy przesunięciu cyklu k = N mod C.

Jeśli N mod C jest równe zero, teraz pasują powoli i szybko, a cykl znajduje się w czasie N i pozycji cyklu k = 0.

Jeśli N mod C nie wynosi zero, to szybko musi teraz dogonić wolne, które w momencie N jest odległością C- (N mod C) w tyle w cyklu.

Ponieważ szybkie ruchy 2 za każde 1 wolnego, zmniejszając odległość o 1 w każdej iteracji, zajmuje to tyle samo dodatkowego czasu, co odległość między szybkimi i wolnymi w czasie N, czyli C- (N mod C). Ponieważ powolne porusza się od przesunięcia 0, jest to również przesunięcie, w którym się spotykają.

Tak więc, jeśli N mod C wynosi zero, faza 1 zatrzymuje się po N iteracjach na początku cyklu. W przeciwnym razie faza 1 zatrzymuje się po iteracjach N + C- (N mod C) z przesunięciem C- (N mod C) do cyklu.

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

Ok, więc faza 2: powolne zajmuje N więcej kroków, aby dostać się do cyklu, w którym to momencie szybki (teraz ruch 1 na krok czasu) jest na (C- (N mod C) + N) mod C = 0. Więc się spotykają na początku cyklu po fazie 2.

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

Aby uzyskać kompletność, faza 3 oblicza długość cyklu, przechodząc jeszcze raz przez cykl:

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}

Zredukuj problem do problemu z pętlą, a następnie wróć do pierwotnego problemu

Poniższe wyjaśnienie wydaje mi się bardziej intuicyjne.

1. Weź dwie wskazówki ( 1 = żółw i 2 = zając), które zaczynają się od głowy ( O ), 1 ma długość kroku 1 , 2 ma długość kroku 2 . Pomyśl o chwili, w której 1 osiąga węzeł początkowy tego cyklu ( A ).

   Chcemy odpowiedzieć na pytanie „Gdzie jest 2, gdy 1 jest w A?” .

   Czyli OA = ajest liczbą naturalną ( a >= 0). Ale można to zapisać w następujący sposób:, a = k*n + bgdzie a, k, n, b are natural numbers:

   • n = długość cyklu
   • k >= 0 = stała
   • 0 <= b <= n-1

   To znaczy, że b = a % n.

   Np .: jeśli a = 20i n = 8=> k = 2i b = 4ponieważ 20 = 2*8 + 4.

   Odległość pokonana przez 1 to d = OA = a = k*n + b. Ale w tym samym czasie 2 okładki D = 2*d = d + d = OA + d = OA + k*n + b. Oznacza to, że gdy 2 jest w A, musi się pokrywać k*n + b. Jak widać, kjest to liczba okrążeń, ale po tych okrążeniach 2 będzie b daleko od A. Więc znaleźliśmy gdzie 2 jest, gdy 1 jest w A. Nazwijmy ten punkt B, gdzie AB = b.

   

2. Teraz sprowadzamy problem do koła. Pytanie brzmi: „Gdzie jest miejsce spotkania?” . Gdzie to jest C ?

   

   Z każdym krokiem 2 zmniejsza odległość od 1 o 1(powiedzmy metr), ponieważ 1 oddala się od 2 z 1, ale jednocześnie 2 zbliża się do 1 o 2.

   Zatem przecięcie będzie miało miejsce, gdy odległość między 1 a 2 będzie wynosić zero. Oznacza to, że 2 zmniejsza n - bodległość. Aby to osiągnąć, 1 zrobi n - bkroki, a 2 zrobi 2*(n - b)kroki.

   Tak więc punkt przecięcia będzie n - bdaleko od A (zgodnie z ruchem wskazówek zegara), ponieważ jest to odległość pokonywana przez 1, aż do spotkania 2 . => odległość między C i A wynosi CA = b, ponieważ AC = AB + BC = n - bi CA = n - AC. Nie myśl, że AC = CAponieważ ACodległość nie jest trywialną odległością matematyczną, jest to liczba kroków między A i C (gdzie A to punkt początkowy, a C to punkt końcowy).

3. Teraz wróćmy do początkowego schematu.

   Wiemy o tym a = k*n + bi CA = b.

   Możemy wziąć 2 nowe wskaźniki 1 ' i 1' ' , gdzie 1' zaczyna się od głowy ( O ), a 1 '' zaczyna się od punktu przecięcia ( C ).

   Podczas gdy 1 ' przechodzi z O do A , 1' ' przechodzi z C do A i kontynuuje kończenie kokrążeń. Więc punkt przecięcia jest .

   

   

Jeśli wskaźniki spotkały się w punkcie P, jak pokazano na rysunku, odległość Z + Y jest punktem P, a X + Y jest również punktem P, co oznacza Z = X. Dlatego utrzymywanie ruchu jednego wskaźnika od punktu P i przesuwanie drugiego od początku (S) do ich spotkania, co oznacza przesunięcie równej odległości (Z lub X) do tego samego punktu M (odległość Z od P i X od S) będzie rozpoczęcie pętli. Prosty!

Biorąc pod uwagę całą powyższą analizę, jeśli jesteś osobą uczącą się na przykładzie, próbowałem napisać krótką analizę i przykład, które pomogą wyjaśnić matematykę, którą wszyscy próbowali wyjaśnić. No to ruszamy!

Analiza:

Jeśli mamy dwa wskaźniki, jeden szybszy od drugiego, i przesuniemy je razem, ostatecznie spotkają się one ponownie, aby wskazać cykl lub wartość zerową, aby wskazać brak cyklu.

Aby znaleźć punkt początkowy cyklu, pozwól ...

1. m być odległością od głowy do początku cyklu;

2. d być liczbą węzłów w cyklu;

3. p1 być prędkością wolniejszego wskaźnika;

4. p2być prędkością szybszego wskaźnika, np. 2 oznacza przejście przez dwa węzły naraz.

   Obserwuj następujące iteracje:

 m = 0, d = 10:
 p1 = 1:  0  1  2  3  4  5  6  7  8  9 10 // 0 would the start of the cycle
 p2 = 2:  0  2  4  6  8 10 12 14 16 18 20

 m = 1, d = 10:
 p1 = 1: -1  0  1  2  3  4  5  6  7  8  9
 p2 = 2: -1  1  3  5  7  9 11 13 15 17 19

 m = 2, d = 10:
 p1 = 1: -2 -1  0  1  2  3  4  5  6  7  8
 p2 = 2: -2  0  2  4  6  8 10 12 14 16 18

Na podstawie powyższych przykładowych danych możemy łatwo stwierdzić, że ilekroć spotykają się szybsze i wolniejsze wskaźniki, są one oddalone o mkilka kroków od początku cyklu. Aby rozwiązać ten problem, umieść szybszą wskazówkę z powrotem w głowicy i ustaw jej prędkość na prędkość wolniejszej wskazówki. Kiedy spotykają się ponownie, węzeł jest początkiem cyklu.

powiedzmy,

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

mamy 2 wskaźniki A i B, A biegnie z prędkością 1x, B z prędkością 2x, oba zaczynają się od początku.

kiedy A osiągnie N [0], B powinno już być w N [m]. (Uwaga: A używa m kroków, aby osiągnąć N [0], a B powinno być m kroków dalej)

Następnie A wykonuje k kolejnych kroków, aby zderzyć się z B, tj. A jest w punkcie N [k], B jest w punkcie N [m + 2k] (Uwaga: B powinien przebiegać przez 2k kroków zaczynając od N [m])

Zderzenie A z B odpowiednio w N [k] i N [m + 2k] oznacza k = m + 2k, czyli k = -m

Tak więc, aby wrócić do N [0] z N [k], potrzebujemy m więcej kroków.

Mówiąc najprościej, po znalezieniu węzła kolizji wystarczy wykonać m więcej kroków. Możemy mieć wskaźnik do uruchomienia od początku i wskaźnik biegnący od węzła kolizji, spotkają się one na N [0] po m krokach.

Dlatego pseudokod jest następujący:

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6

Nie sądzę, żeby to prawda, że ​​kiedy się spotykają, to jest punkt wyjścia. Ale tak, jeśli drugi wskaźnik (F) znajdował się wcześniej w miejscu spotkania, to ten wskaźnik będzie na końcu pętli zamiast na początku pętli, a wskaźnik (S), który rozpoczął się od początku listy, będzie kończą się na początku pętli. na przykład:

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8

Meet at :16

Start at :8

public Node meetNodeInLoop(){

    Node fast=head;
    Node slow=head;

    fast=fast.next.next;
    slow=slow.next;

    while(fast!=slow){

        fast=fast.next;
        fast=fast.next;

        if(fast==slow) break; 

        slow=slow.next;
    }

    return fast;

}

public Node startOfLoop(Node meet){

    Node slow=head;
    Node fast=meet;

    while(slow!=fast){
        fast=fast.next;
        if(slow==fast.next) break;
        slow=slow.next;
    }

    return slow;
}

Proste wyjaśnienie z wykorzystaniem idei prędkości względnej nauczanej w liceum - wykład Fizyka 101 / Kinematyka.

1. Załóżmy, że odległość od początku połączonej listy do początku okręgu to xprzeskoki. Nazwijmy początek okręgu punktem X(wielkimi literami - patrz rysunek powyżej). Przyjmijmy również, że całkowity rozmiar koła to N przeskoków.

2. Prędkość zająca = 2 * Prędkość żółwia. Więc to jest 1 hops/seci 2 hops/secodpowiednio

3. Kiedy żółw osiągnie początek koła X, zając musi dalej xprzeskakiwać w miejscu Yna rysunku. (Ponieważ zając przebył dwukrotnie większą odległość niż żółw).

4. Zatem długość pozostałego łuku zgodnie z ruchem wskazówek zegara od X do Y byłaby N-x. Tak się składa, że ​​jest to również względna odległość, jaką należy pokonać między zającem a żółwiem, aby mogły się spotkać . Powiedzmy, że ta względna odległość zostanie pokonana w czasie, t_mtj. W czasie do spotkania. Względna prędkość to (2 hops/sec - 1 hops/sec)np 1 hops/sec. Zatem używając, odległość względna = prędkość względna X czas, otrzymujemy t= N-xsek. Tak więc zajmie N-xto dotarcie do miejsca spotkania zarówno żółwia, jak i zająca.

5. Teraz za N-xsekundę iz 1 hops/secdużą prędkością żółw, który był wcześniej na miejscu X, pokona skok Nx, aby dotrzeć do miejsca spotkania M. Oznacza to, że punkt spotkania Mznajduje się w N-xprzeskokach w kierunku przeciwnym do ruchu wskazówek zegara od X= (co dalej oznacza) =>, że xpozostała odległość od punktu Mdo Xruchu wskazówek zegara.

6. Ale xjest to także odległość do punktu Xod początku połączonej listy.

7. Teraz nie obchodzi nas, jaka xodpowiada liczbie przeskoków . Jeśli umieścimy jednego żółwia na początku LinkedList i jednego żółwia w miejscu spotkania Mi pozwolimy im skakać / chodzić, spotkają się w punkcie X, który jest punktem (lub węzłem), którego potrzebujemy.

Pomocna byłaby praca z diagramem. Próbuję wyjaśnić problem bez równań.

1. Jeśli pozwolimy zającowi i żółwiowi biegać w kółko, a zając biegnie dwa razy żółw, to na końcu jednego okrążenia zając żółw będzie miał połowę. Na końcu dwóch okrążeń żółw zając zrobiłby 1 okrążenie i obaj się spotykają. Odnosi się to do wszystkich prędkości, jak gdyby zając biegł trzy razy, zając 1 okrążenie równa się 1/3 żółwia, więc na końcu 3 okrążeń żółw zająłby 1 okrążenie i spotykają się.
2. Jeśli zaczniemy je m kroków przed pętlą, to znaczy, że szybszy zając zaczyna w pętli. Więc jeśli żółw dotrze do początku pętli, zając jest m kroków do przodu pętli, a kiedy się spotkają, będzie to m kroków przed początkiem pętli.

-jest k kroków przed pętlą. Nie wiemy, czym jest k i nie musimy się tego dowiadywać. Możemy pracować abstrakcyjnie, używając tylko k.

--Po k kroków

----- T jest na początku cyklu

----- H to k kroków w cyklu (przeszedł łącznie 2k, a zatem k w pętlę)

** mają teraz rozmiar pętli - k od siebie

(zwróć uwagę, że k == K == mod (loopsize, k) - np. jeśli węzeł jest 2 kroki w cyklu 5 węzłów, to również 7, 12 lub 392 kroki, więc jak duży jest cykl, k nie czynnik w.

Ponieważ dogonią się w tempie 1 kroku na jednostkę czasu, ponieważ jeden porusza się dwa razy szybciej niż drugi, spotkają się przy rozmiarze pętli - k.

Oznacza to, że osiągnięcie początku cyklu zajmie k węzłów, a zatem odległość od głowy do początku cyklu i kolizji do początku cyklu jest taka sama.

Więc teraz po pierwszym zderzeniu przenieś T z powrotem do głowy. T i H spotkają się na początku cyklu, jeśli poruszasz się w tempie 1 każdy. (w k krokach dla obu)

Oznacza to, że algorytm to:

• od głowy przesuń T = t.next i H.next.next, aż zderzą się (T == H) (istnieje cykl)

// zajmij się przypadkiem, gdy k = 0 lub T i H spotkały się na początku pętli, obliczając długość pętli

- policz długość cyklu, przesuwając T lub H wokół niego za pomocą licznika

- przenieś wskaźnik T2 na początek listy

- przesuń wskaźnik długości kroków cyklu

- przesuń kolejny wskaźnik H2 do głowy

- przesuń T2 i H2 w tandemie, aż spotkają się na początku cyklu

Otóż ​​to!

Odpowiedzi na to jest już wiele, ale kiedyś wymyśliłem diagram, który jest dla mnie bardziej intuicyjny wizualnie. Być może pomoże innym ludziom.

Głównymi momentami aha dla mnie były:

• Podziel T (żółw) na T1 (przed pętlą) i T2 (w pętli).

• Odejmij T od H , gdzie wizualnie się nakładają. Co zostało ( H - T = H” ) wynosi T .

• Pozostała matematyka jest dość prosta.

Wiem, że istnieje już zaakceptowana odpowiedź na ten problem, ale nadal będę starał się odpowiadać w sposób płynny. Założyć :

The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. 
    Speed of tortoise : v
    Speed of hare     : 2*v 
    Point where both meet is at a distance 'x + b - k' from the starting point.

Teraz pozwól zającowi i żółwiowi spotkać się po czasie „t” od początku.

Obserwacje:

Jeśli, odległość przebyta przez żółwia = v * t = x + (bk) (powiedzmy)

Wówczas Odległość przebyta przez zająca = 2 * v * t = x + (b - k) + b (ponieważ zając przeszedł już raz zapętloną część)

Teraz czasy spotkań są takie same.

=> x + 2 * b - k = 2 * (x + b - k)

=> x = k

Oznacza to oczywiście, że długość ścieżki, która nie jest zapętlona, ​​jest taka sama, jak odległość punktu początkowego pętli od punktu, w którym oba się spotykają.

W rzeczywistości łatwo jest udowodnić, że obaj spotkają się na początku, jeśli weźmiesz pod uwagę matematykę za miejscem spotkania.
Najpierw niech m oznacza punkt początkowy cyklu na połączonej liście, a n oznacza długość cyklu. Następnie na spotkanie zająca i żółwia mamy:

( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)

Mówiąc bardziej matematycznie:

(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

więc spotkają się w czasie t, który powinien być wielokrotnością długości cyklu. Oznacza to, że spotykają się w miejscu, którym jest (t-m) modulo n = (0-m) modulo n = (-m) modulo n.

Wracając teraz do pytania, jeśli przesuniesz jeden wskaźnik z początku połączonej listy, a drugi z punktu przecięcia, po m krokach zając (który porusza się w cyklu) dojdzie do punktu ((-m) + m) modulo n = 0 modulo nco jest niczym innym jak początkiem cyklu, więc widzimy, że po m krokach dochodzi do początku cyklu i żółw go tam spotka, pokonując m kroków od początku połączonej listy.

Na marginesie, możemy również obliczyć czas ich przecięcia się w następujący sposób: Warunek t = 0 modulo nmówi nam, że spotkają się w czasie, który jest wielokrotnością długości cyklu, a także t powinno być większe niż m, ponieważ spotkałyby się w cykl. Zatem potrzebny czas będzie równy pierwszej wielokrotności n, która jest większa niż m .

Załóżmy, że twoje wskaźniki spotykają się na przecięciu punktu y i z.

n i m to odpowiednio liczba pętli, które są odpowiednio szybsze i wolniejsze przed spotkaniem.

Resztę dowodu znajdziesz na obrazku. Znajdź punkt początkowy pętli na połączonej liście