Linked List Cycle

Q: Jaka jest złożoność czasowa i pamięciowa problemu cyklu w liście połączonej?

Oba podejścia wymagają czasu O(n) , ponieważ każdy węzeł jest odwiedzany ograniczoną liczbę razy. Oznaczanie odwiedzonych węzłów wymaga dodatkowej pamięci O(n) . Szybki i wolny wskaźnik Floyda wymagają O(1) : dwóch numerów węzłów.

Q: Dlaczego szybki wskaźnik nie może przeskoczyć wolnego wskaźnika?

Wewnątrz cyklu w każdej rundzie fast przesuwa się o dwa węzły, a slow o jeden, więc odległość, jaką fast musi jeszcze pokonać, aby dotrzeć do slow , zmniejsza się dokładnie o jeden. Odległość, która zmniejsza się o jeden w każdej rundzie, wynosi kolejno 3, 2, 1, 0 i nie może przejść poniżej zera, więc oba wskaźniki spotykają się na węźle.

Q: Czy potrafisz wykryć cykl, licząc kroki?

W tej postaci tablicy — tak: lista bez cyklu dochodzi do -1 w ciągu n łączy, więc przejście przez n łączy bez dotarcia do końca dowodzi istnienia cyklu, przy użyciu O(1) pamięci. Ta metoda wymaga liczby węzłów, której nie można uzyskać z listy złożonej ze wskaźników, a wcześniejsze ich zliczanie nigdy się nie kończy, gdy lista zawiera cykl. Metoda Floyda nie wymaga zliczania.

ŁatweSzybki i wolny wskaźnik Lista wiązana

+10

Lista jednokierunkowa jest przechowywana w tablicy next: węzeł i prowadzi do węzła next[i], a -1 oznacza koniec listy. Głową jest węzeł 0. Podążaj za połączeniami od głowy i zwróć true, jeśli wrócisz do węzła, który został już odwiedzony, lub false, jeśli dotrzesz do końca. Węzły, do których nigdy nie dotrzesz, nie mają znaczenia, nawet jeśli łączą się ze sobą w pętlę.

Funkcja

hasCycle(next: integer-array) → boolean

nextinteger-array: następnik każdego węzła: next[i] to węzeł znajdujący się po węźle i albo -1
Zwracaboolean: true, jeśli przejście od węzła 0 ponownie odwiedza węzeł, false, jeśli dociera do -1

Ograniczenia

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Kilka węzłów może prowadzić do tego samego węzła, a niektóre węzły mogą być nieosiągalne z głowy.

Przykłady

Wejście: next = [1, 2, 3, 1]
Wyjście: true
Wyjaśnienie: Przejście przebiega przez 0, 1, 2, 3, a następnie wraca do 1. Węzeł 1 jest odwiedzany dwukrotnie, więc lista zawiera cykl przechodzący przez węzły 1, 2 i 3.

Wejście: next = [2, -1, 1]
Wyjście: false
Wyjaśnienie: Ścieżka przebiega przez 0, 2, 1, a następnie dociera do -1: trzy różne węzły, a potem koniec, więc nie ma cyklu.

Wejście: next = [-1, 2, 1]
Wyjście: false
Wyjaśnienie: Węzeł 0 wskazuje na -1, więc lista ma długość jednego węzła. Węzły 1 i 2 wskazują na siebie nawzajem, tworząc pętlę, ale przejście od głowy listy nigdy do nich nie dociera.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz również znaleźć węzeł, w którym zaczyna się cykl, nadal używając dodatkowej pamięci O(1)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Lista bez cyklu osiąga -1 po przejściu przez n łączy, ale lista z cyklem nigdy się nie kończy, więc nie możesz czekać na koniec. Potrzebujesz sposobu, by zauważyć, że przechodzisz tę samą trasę. Zapamiętanie każdego odwiedzanego węzła wymaga pamięci O(n). Szybkie i wolne wskaźniki Floyda pozwalają to zrobić za pomocą dwóch liczb całkowitych, ponieważ wskaźnik poruszający się dwa razy szybciej musi dogonić wolniejszy wewnątrz pętli.

Oznacz odwiedzane węzły

Intuicja

Wyrusz z węzła 0 i oznaczaj każdy węzeł, gdy go opuszczasz. Jeśli dotrzesz do węzła, który jest już oznaczony, oznacza to, że ścieżka do niego wróciła, a od tego momentu będzie się powtarzać w nieskończoność: to cykl. W przykładzie 1 oznaczasz węzły 0, 1, 2 i 3, a połączenie z węzła 3 prowadzi do węzła 1, który jest oznaczony.

Węzły są ponumerowane od 0 do n-1, więc tablica wartości logicznych o długości n służy jako zbiór odwiedzonych węzłów. W liście połączonej zbudowanej z obiektów zamiast tego umieszczasz referencje do węzłów w zbiorze haszującym; pomysł jest taki sam.

Każdy węzeł jest oznaczany najwyżej raz, a ścieżka kończy się przy pierwszym powtórzeniu lub przy -1, więc zajmuje najwyżej n kroków: czas O(n) i pamięć O(n) na oznaczenia.

Algorytm

Utwórz tablicę wartości logicznych visited o długości n, wypełnioną wartościami false.
Ustaw node = 0.
Gdy node nie jest równe -1, zwróć true, jeśli visited[node] ma już wartość true.
W przeciwnym razie ustaw visited[node] i przejdź do next[node].
Gdy przechodzenie dotrze do -1, zwróć false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Szybkie i wolne wskaźniki (wykrywanie cyklu Floyda)

Intuicja

Ustaw dwa wskaźniki na początku. slow przechodzi jedno łącze w każdej rundzie, a fast — dwa. Jeśli lista się kończy, fast jako pierwszy dociera do -1 i zwracasz false. Jeśli istnieje cykl, fast jako pierwszy do niego wchodzi i krąży w nim, aż slow również dotrze na miejsce.

Gdy oba wskaźniki znajdą się w cyklu, w każdej rundzie fast zyskuje dokładnie jeden węzeł względem slow. Odległość, jaką fast musi jeszcze pokonać, aby dotrzeć do slow, zmniejsza się o jeden w każdej rundzie, więc w końcu wynosi zero, a wskaźniki wskazują ten sam węzeł. Zyskując po jednym węźle naraz, fast nigdy nie może przeskoczyć nad slow.

W przykładzie 1 po jednej rundzie slow wskazuje węzeł 1, a fast — węzeł 2. Po dwóch rundach slow wskazuje węzeł 2, a fast przeszedł przez węzły 3 i 1. Po trzech rundach oba wskaźniki wskazują węzeł 3, więc odpowiedź to true.

slow potrzebuje co najwyżej n rund, aby wejść do cyklu, a gdy już się w nim znajdzie, wskaźniki spotkają się, zanim wykona pełne okrążenie, więc złożoność czasowa wynosi O(n). Potrzebna jest pamięć jedynie na dwa numery węzłów.

Algorytm

Ustaw slow = 0 i fast = 0.
Dopóki fast nie jest równe -1 i next[fast] nie jest równe -1, przesuwaj slow o jedno ogniwo, a fast o dwa ogniwa.
Po każdym przesunięciu zwróć true, jeśli znajdują się na tym samym węźle.
Gdy pętla się zatrzyma, fast dotarło do końca: zwróć false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Pułapki i przypadki brzegowe

Ukryte błędy dotyczą końca listy oraz tego, które węzły się liczą.

Przesunięcie fast o dwa łącza bez sprawdzenia obu. Zarówno fast, jak i next[fast] muszą wskazywać rzeczywiste węzły, zanim odczytasz next[next[fast]]; w przeciwnym razie odczytasz next[-1], co powoduje awarię w większości języków i po cichu zwraca ostatni element w Pythonie.
Porównywanie wskaźników przed ich przesunięciem. Oba zaczynają w węźle 0, więc sprawdzenie na początku pętli zgłasza cykl na każdej liście.
Sprawdzanie całej tablicy zamiast przejścia po niej. W [-1, 2, 1] węzły 1 i 2 tworzą pętlę, ale ścieżka od głowy kończy się od razu, więc odpowiedzią jest false. Błędne jest również sprawdzanie, czy wartość powtarza się w next: w [4, 4, 4, 4, -1] kilka węzłów wskazuje węzeł 4, ale nie ma cyklu.
Zakładanie, że cykl musi prowadzić z powrotem do głowy. W [1, 2, 3, 4, 4] ostatni węzeł wskazuje na siebie, a w [0] robi to głowa.

Najczęstsze pytania4

Jak działa algorytm Floyda wykrywający cykle?

Dwa wskaźniki zaczynają od głowy: jeden przesuwa się o jedno ogniwo na krok, a drugi o dwa. Jeśli nie ma cyklu, szybszy wskaźnik dociera do końca. Jeśli cykl istnieje, oba wskaźniki trafiają do niego, szybszy zmniejsza dzielącą je odległość o jeden węzeł na krok i spotykają się w tym samym węźle.

Jaka jest złożoność czasowa i pamięciowa problemu cyklu w liście połączonej?

Oba podejścia wymagają czasu O(n), ponieważ każdy węzeł jest odwiedzany ograniczoną liczbę razy. Oznaczanie odwiedzonych węzłów wymaga dodatkowej pamięci O(n). Szybki i wolny wskaźnik Floyda wymagają O(1): dwóch numerów węzłów.

Dlaczego szybki wskaźnik nie może przeskoczyć wolnego wskaźnika?

Wewnątrz cyklu w każdej rundzie fast przesuwa się o dwa węzły, a slow o jeden, więc odległość, jaką fast musi jeszcze pokonać, aby dotrzeć do slow, zmniejsza się dokładnie o jeden. Odległość, która zmniejsza się o jeden w każdej rundzie, wynosi kolejno 3, 2, 1, 0 i nie może przejść poniżej zera, więc oba wskaźniki spotykają się na węźle.

Czy potrafisz wykryć cykl, licząc kroki?

W tej postaci tablicy — tak: lista bez cyklu dochodzi do -1 w ciągu n łączy, więc przejście przez n łączy bez dotarcia do końca dowodzi istnienia cyklu, przy użyciu O(1) pamięci. Ta metoda wymaga liczby węzłów, której nie można uzyskać z listy złożonej ze wskaźników, a wcześniejsze ich zliczanie nigdy się nie kończy, gdy lista zawiera cykl. Metoda Floyda nie wymaga zliczania.

Python

def hasCycle(next):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

next = [1, 2, 3, 1]

Oczekiwane

true