wykrywanie początku pętli w pojedynczo połączonej liście linków?

Krok 1: Postępuj w zwykły sposób, użyjesz do znalezienia pętli, tzn. Mają dwa wskaźniki, przyrost jeden w jednym kroku, a drugi w dwóch krokach, jeśli oba spotykają się kiedyś, istnieje pętla.

Krok 2: Zatrzymaj jeden wskaźnik tam, gdzie był i zwiększ drugi wskaźnik w jednym kroku zliczając wykonane kroki, a gdy oba spotkają się ponownie, licznik poda długość pętli (jest to takie samo, jak zliczanie liczby elementów w łączu kołowym lista).

Krok 3: Zresetuj oba wskaźniki do początku listy linków, zwiększ jeden wskaźnik do długości czasów pętli, a następnie uruchom drugi wskaźnik. zwiększ oba wskaźniki w jednym kroku, a gdy spotkają się ponownie, będzie to początek pętli (jest to takie samo jak znalezienie N^th elementu z końca listy linków).

DOWÓD MATEMATYCZNY + ROZWIĄZANIE

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

Prosty przypadek: gdy k

Gdy wskaźnik " P "znajdowałby się w BEGINLOOP (tzn. przebyłby kroki "k"), Q przebyłby kroki "2k". Tak więc, Q jest przed' 2K-K = K 'kroków od P, Gdy P wchodzi w pętlę, a zatem, Q jest' n-k ' kroki za BEGINLOOP teraz.

Gdy P przemieszczałby się z BEGINLOOP do MEETPONT, przebyłby kroki "m-k". W tym czasie Q podróżował "2 (m-k)" kroki. Ale odkąd się spotkali, A Q zaczął' n-k ' kroki za BEGINLOOP, więc, skutecznie, "2 (m-k) - (n-k)" powinno być równe " (m-k)" Więc

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

Oznacza to, że P I Q spotykają się w punkcie równym liczbie kroków (lub wielokrotności, aby być ogólnym, patrz przypadek opisany poniżej) w pętli. Teraz, na MEETPOINCIE, zarówno P jak i Q są "N-(m-k)" krokami w tył, czyli " k " krokami w tył, jak widzieliśmy n = m. Jeśli więc zaczniemy P od nagłówka, A Q od punktu spotkania, ale tym razem z Tempo równe P, P I Q będzie teraz spotykane tylko na BEGINLOOP.

Przypadek ogólny: powiedzmy, k = nX + Y , Y (Stąd k % n = Y)

Gdy wskaźnik " P "znajdowałby się w BEGINLOOP (tzn. przebyłby kroki "k"), Q przebyłby kroki "2k". Tak więc, efektywnie, Q jest przed' 2K-K = k ' kroków od P, Gdy P wchodzi w pętlę. Należy jednak pamiętać, że 'k' jest większe niż 'n', co oznacza, że Q wykonałoby wiele rund pętli. Czyli w praktyce Q to "n-(k%n)" kroki za BEGINLOOP teraz.

Gdy P przemieszczałby się z BEGINLOOP do MEETPOINT, przebyłby kroki "m-k". (Stąd, w praktyce, MEETPOINT będzie NA "(m-k)%n " kroków przed BEGINLOOP teraz.) W tym czasie Q przebył "2 (m-k)" kroki. Ale, ponieważ się spotkali, A Q zaczął 'n-(k%n)' kroki za BEGINLOOP, więc, efektywnie, nowa pozycja Q(która jest '(2 (m-k) - (n-k/%n))%n' od BEGINLOOP) powinna być równa nowej pozycji P(która jest '(m-k)%n' od BEGINLOOP) powinna być równa nowej pozycji P (która jest '(m-k) % n ' od BEGINLOOP LOOP).

Więc,

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Najpierw staramy się dowiedzieć, czy jest jakaś pętla w liście, czy nie. Jeśli pętla istnieje, to staramy się znaleźć punkt początkowy pętli. W tym celu używamy dwóch wskaźników: slowPtr i fastPtr. W pierwszej detekcji (sprawdzanie pętli), fastPtr porusza się o dwa kroki na raz, ale slowPtr porusza się o jeden krok do przodu na raz.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

Jest jasne, że jeśli w liście jest jakaś pętla, to spotkają się one w punkcie (Punkt 7 na powyższym obrazku), ponieważ wskaźnik fastPtr jest uruchomiony dwa razy szybciej niż inne.

Teraz dochodzimy do drugiego problemu znalezienia punktu początkowego pętli.

Załóżmy, że spełniają się w punkcie 7 (Jak wspomniano na powyższym obrazku). Następnie slowPtr wychodzi z pętli i stoi na początku listy oznacza w punkcie 1, ale fastPtr nadal w miejscu spotkania (Punkt 7). Teraz porównujemy wartość obu wskaźników, jeśli są takie same, to jest to punkt początkowy pętli w przeciwnym razie poruszamy się o jeden krok do przodu (tutaj fastPtr porusza się również o jeden krok za każdym razem) i porównujemy ponownie do znajdujemy ten sam punkt.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

Przypuśćmy:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

Więcej szczegółów tutaj

Postępuj w zwykły sposób, którego użyjesz do znalezienia pętli. ie. Mają dwa wskaźniki, increment jeden w jednym kroku (slowPointer) i inne w dwóch krokach (fastPointer), jeśli oba spotykają się kiedyś, istnieje pętla.

Jak mogłeś już sobie uświadomić, że punkt spotkania to krok k przed głową pętli.

Gdzie k jest wielkością nie zapętlonej części listy.

Teraz przesuń powoli do głowy pętli

Trzymaj się szybko w miejscu kolizji

Każdy z nich jest krok k Od początku pętli (wolny od początku listy, gdzie tak szybki jest krok k przed głową pętli-narysuj zdjęcie, aby uzyskać jasność)

Teraz przesuń je z tą samą prędkością - muszą się spotkać na początku pętli

Eg

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

Jest to kod do znalezienia początku pętli na liście linked:

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

Istnieją dwa sposoby znajdowania pętli na liście linków. 1. Użyj dwóch wskaźników jeden krok naprzód jeden krok i drugi krok dwa kroki jeśli istnieje pętla, w pewnym punkcie oba wskaźniki otrzymują tę samą wartość i nigdy nie osiągają wartości null. Ale jeśli nie ma wskaźnika pętli osiąga wartość null w jednym punkcie i oba wskaźniki nigdy nie otrzymują tej samej wartości. Ale w tym podejściu możemy uzyskać tam jest pętla na liście linków, ale nie możemy powiedzieć, gdzie dokładnie rozpoczyna się pętla. Nie jest to również skuteczny sposób.

1. Użyj funkcja hash w taki sposób, aby wartość była unikalna. Incase jeśli staramy się wstawić duplikat powinien przez wyjątek. Następnie przejdź przez każdy węzeł i wciśnij adres do hash. Jeśli wskaźnik osiągnie wartość null i brak wyjątku od hasha oznacza, że na liście odnośników nie ma cyklu. Jeśli otrzymujemy jakikolwiek wyjątek od hash oznacza to, że na liście znajduje się cykl i jest to link, z którego cykl się rozpoczyna.

Cóż, wypróbowałem sposób, używając jednego wskaźnika... Wypróbowałem metodę w kilku zestawach danych.... Ponieważ pamięć dla każdego z węzłów połączonej listy jest przydzielana w rosnącej kolejności, więc podczas przechodzenia przez połączoną listę od głowicy połączonej listy, jeśli adres węzła staje się większy niż adres węzła, do którego wskazuje, możemy określić, że istnieje pętla, a także element początkowy pętli.

Najlepsza odpowiedź jaką znalazłem była tutaj:
tianrunhe: find-loop-starting-point-in-a-circular-linked-list

• ' M ' jest odległością między głową a START_LOOP
• 'L' jest długością pętli
• 'd' jest odległością między MEETING_POINT i START_LOOP

• P1 porusza się przy V, A P2 porusza się przy 2 * V

  Gdy spotkają się dwa wskaźniki: bieg dystansowy to = m+ n*L-d = 2*(m+ L-d)

  = > czyli (nie matematycznie udowodnione tutaj), że jeśli p1 zaczyna się od HEAD & P2 zaczyna się od MEETING_POINT i poruszają się w tym samym tempie, spotkają @ START_LOOP

Zobacz Ten link, aby uzyskać wyczerpującą odpowiedź.

1. Postępuj w zwykły sposób, którego użyjesz, aby znaleźć pętlę. ie. Mają dwa wskaźniki, przyrost jeden w jednym kroku, a drugi w dwóch krokach, jeśli oba spotykają się kiedyś, istnieje pętla.

2. Zachowaj jeden ze wskaźników stały uzyskaj całkowitą liczbę węzłów w pętli powiedz L.

3. Teraz z tego punktu (przyrost drugi wskaźnik do następnego węzła w pętli) w pętli Odwróć połączoną listę i policz liczbę węzłów przejechanych, powiedzmy X.

4. Teraz za pomocą drugiego wskaźnika (pętla jest przerwana) z tego samego punktu w pętli travrse połączoną listę i policzyć liczbę pozostałych węzłów powiedzieć Y

5. Pętla rozpoczyna się po ((X+Y)-L)\2 węzłach. Lub zaczyna się od ((((X+Y)-L)\2+1)węzła.

1. Postępuj w zwykły sposób, którego użyjesz, aby znaleźć pętlę. ie. Mają dwa wskaźniki, przyrost jeden w jednym kroku, a drugi w dwóch krokach, jeśli oba spotykają się kiedyś, istnieje pętla.

2. Zachowaj jeden ze wskaźników stały uzyskaj całkowitą liczbę węzłów w pętli powiedz L.

3. Teraz z tego punktu (przyrost drugi wskaźnik do następnego węzła w pętli) w pętli Odwróć połączoną listę i policz liczbę węzłów przejechanych, powiedzmy X.

4. Teraz za pomocą drugiego wskaźnika (pętla jest przerwana) z tego samego punktu w pętli travrse połączoną listę i policzyć liczbę pozostałych węzłów powiedzieć Y

5. Pętla rozpoczyna się po ((X+Y)-L)\2 węzłach. Lub zaczyna się od ((((X+Y)-L)\2+1)węzła.

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

1. detect loop
2. skopiuj adres każdego elementu do zestawu. Jeśli zostanie znaleziony duplikat, to początek pętli