Załóżmy, że masz połączoną strukturę listy w Javie. Składa się z węzłów:
class Node {
Node next;
// some user data
}
i każdy Węzeł wskazuje na następny węzeł, z wyjątkiem ostatniego Węzła, który ma wartość null dla następnego. Powiedzmy, że istnieje możliwość, że lista może zawierać pętlę - tj. Końcowy Węzeł, zamiast mieć wartość NULL, ma odniesienie do jednego z węzłów na liście, który był przed nim.
Jaki jest najlepszy sposób pisania
boolean hasLoop(Node first)
co by zwróciło, true
gdyby dany Węzeł był pierwszym z listy z pętlą, a w false
przeciwnym razie? Jak mogłeś pisać, aby zajmowała stałą ilość miejsca i rozsądną ilość czasu?
Oto zdjęcie, jak wygląda lista z pętlą:
java
algorithm
data-structures
linked-list
jjujuma
źródło
źródło
finite amount of space and a reasonable amount of time?
:)Odpowiedzi:
Możesz skorzystać z algorytmu Floyda znajdującego cykl , znanego również jako algorytm żółwia i zająca .
Chodzi o to, aby mieć dwa odniesienia do listy i przenosić je z różnymi prędkościami . Przesuwaj jeden do przodu o
1
węzeł, a drugi o2
węzły.next
)null
.Funkcja Java implementująca algorytm:
źródło
fast.next
Przednext
ponownym dzwonieniem należy również wykonać kontrolę zerową :if(fast.next!=null)fast=fast.next.next;
Oto udoskonalenie rozwiązania Fast / Slow, które poprawnie obsługuje listy nieparzystych długości i poprawia przejrzystość.
źródło
slow == fast.next
toslow
będzie równefast
przy następnej iteracji; oszczędza tylko jedną iterację najwyżej kosztem dodatkowego testu dla każdej iteracji.slow
nie może stać się wcześniej zerowy,fast
ponieważ podąża tą samą ścieżką referencji (chyba że masz jednoczesną modyfikację listy, w którym to przypadku wszystkie zakłady są wyłączone).Lepszy niż algorytm Floyda
Richard Brent opisał alternatywny algorytm wykrywania cyklu , który jest podobny do zająca i żółwia [cykl Floyda], z wyjątkiem tego, że wolny węzeł tutaj się nie porusza, ale jest później „teleportowany” do pozycji szybkiego węzła na stałym poziomie interwały.
Opis jest dostępny tutaj: http://www.siafoo.net/algorithm/11 Brent twierdzi, że jego algorytm jest 24 do 36% szybszy niż algorytm cyklu Floyda. O (n) złożoność czasu, O (1) złożoność przestrzeni.
źródło
slow.next != null
? O ile widzęslow
jest zawsze z tyłu lub równafast
.Alternatywne rozwiązanie dla Żółwia i Królika, niezbyt miłe, ponieważ tymczasowo zmieniam listę:
Chodzi o to, aby przejrzeć listę i odwrócić ją w trakcie podróży. Następnie, gdy pierwszy raz dotrzesz do węzła, który już był odwiedzany, jego następny wskaźnik będzie wskazywał „do tyłu”, powodując, że iteracja zacznie się
first
ponownie w kierunku , w którym się kończy.Kod testowy:
źródło
Żółw i zając
Spójrz na algorytm rho Pollarda . Nie jest to ten sam problem, ale być może zrozumiesz logikę z niego i zastosujesz go do list połączonych.
(jeśli jesteś leniwy, możesz po prostu sprawdzić wykrywanie cyklu - sprawdź część dotyczącą żółwia i zająca).
Wymaga to tylko czasu liniowego i 2 dodatkowych wskaźników.
W Javie:
(Większość rozwiązań nie sprawdza zarówno dla zer, jak
next
inext.next
dla zer. Ponadto, ponieważ żółw jest zawsze z tyłu, nie musisz go sprawdzać pod kątem zerowości - zając już to zrobił.)źródło
Unicornaddict użytkownika ma fajny algorytm powyżej, ale niestety zawiera błąd w listach niepętlowych o nieparzystej długości> = 3. Problem polega na tym, że
fast
może utknąć tuż przed końcem listy,slow
łapie go i pętla jest (błędnie) wykrywana.Oto poprawiony algorytm.
źródło
W tym kontekście wszędzie jest mnóstwo materiałów tekstowych. Chciałem tylko zamieścić schematyczną reprezentację, która naprawdę pomogła mi zrozumieć tę koncepcję.
Kiedy szybkie i wolne spotykają się w punkcie p,
Przebyta odległość = a + b + c + b = a + 2b + c
Przebyty powolny dystans = a + b
Ponieważ szybki jest 2 razy szybszy niż wolny. Więc a + 2b + c = 2 (a + b) , a następnie otrzymujemy a = c .
Tak więc, gdy kolejny wolny wskaźnik ponownie uruchomi się od głowy do q , jednocześnie szybki wskaźnik będzie przebiegał od p do q , więc spotykają się w punkcie q razem.
źródło
a
jest większa niż długość pętli, wówczas szybkie utworzy wiele pętli, a formuładistance (fast) = a + b + b + c
zmieni się naa + (b+c) * k + b
wprowadzenie dodatkowego parametru,k
który zlicza liczbę lopps wykonanych przez szybki.Algorytm
Złożoność
źródło
n
naprawioneequals
ihashCode
. To nie to samo. I to wykluczanull
ostatni element. Pytanie nie mówiło nic o przechowywaniu węzłów wLinkedList
.Poniższa metoda może nie być najlepszą metodą - jest to O (n ^ 2). Powinno to jednak służyć do wykonania zadania (ostatecznie).
źródło
Wybacz mi moją ignorancję (wciąż jestem całkiem nowy w Javie i programowaniu), ale dlaczego powyższe nie zadziałałoby?
Myślę, że to nie rozwiązuje stałego problemu z przestrzenią ... ale przynajmniej dotrze tam w rozsądnym czasie, prawda? Zajmie tylko przestrzeń połączonej listy plus przestrzeń zestawu z n elementami (gdzie n jest liczbą elementów na połączonej liście lub liczbą elementów, dopóki nie osiągnie pętli). I na razie, moim zdaniem, analiza najgorszego przypadku sugerowałaby O (nlog (n)). Wyszukiwania SortedSet dla zawiera () są log (n) (sprawdź javadoc, ale jestem pewien, że podstawową strukturą TreeSet jest TreeMap, którego z kolei jest czerwono-czarne drzewo), aw najgorszym przypadku (bez pętli, lub zapętlić na samym końcu), będzie musiał wykonać n przeglądów.
źródło
Jeśli pozwolimy osadzić klasę
Node
, rozwiązałbym problem, ponieważ zaimplementowałem go poniżej.hasLoop()
działa w czasie O (n) i zajmuje tylko przestrzeńcounter
. Czy to wydaje się odpowiednie rozwiązanie? A może jest to zrobić bez osadzaniaNode
? (Oczywiście w prawdziwej implementacji byłoby więcej metod, takich jakRemoveNode(Node n)
itp.)źródło
Możesz to zrobić nawet w stałym czasie O (1) (choć nie byłoby to zbyt szybkie ani wydajne): istnieje ograniczona liczba węzłów w pamięci komputera, na przykład N rekordów. Jeśli przejdziesz więcej niż N rekordów, masz pętlę.
źródło
źródło
Użyj powyższej funkcji, aby wykryć pętlę na liście połączonych w java.
źródło
Wykrywanie pętli na połączonej liście można wykonać na jeden z najprostszych sposobów, co powoduje złożoność O (N) przy użyciu mapy skrótów lub O (NlogN) przy użyciu podejścia opartego na sortowaniu.
Przechodząc przez listę zaczynając od głowy, utwórz posortowaną listę adresów. Po wstawieniu nowego adresu sprawdź, czy adres już tam jest na posortowanej liście, co wymaga złożoności O (logN).
źródło
Nie widzę żadnego sposobu, aby to zajęło określoną ilość czasu lub miejsca, oba wzrosną wraz z rozmiarem listy.
Korzystałbym z IdentityHashMap (biorąc pod uwagę, że nie ma jeszcze IdentityHashSet) i zapisywałbym każdy Węzeł na mapie. Zanim węzeł zostanie zapisany, wywołujesz na nim zawiera klucz. Jeśli węzeł już istnieje, masz cykl.
ItentityHashMap używa == zamiast .equals, dzięki czemu sprawdzasz, gdzie znajduje się obiekt w pamięci, a nie czy ma taką samą zawartość.
źródło
Mogę być strasznie spóźniony i nowy, aby poradzić sobie z tym wątkiem. Ale nadal…
Dlaczego nie można adresu węzła i wskazanego „następnego” węzła przechowywać w tabeli
Gdybyśmy mogli w ten sposób przedstawić tabelę
Dlatego powstaje cykl.
źródło
Oto mój kod do uruchomienia.
To, co zrobiłem, to ujawnienie połączonej listy za pomocą trzech tymczasowych węzłów (złożoność przestrzeni
O(1)
), które śledzą łącza.Ciekawym faktem jest to, że pomaga wykryć cykl na połączonej liście, ponieważ w miarę postępu nie spodziewasz się powrotu do punktu początkowego (węzła głównego), a jeden z tymczasowych węzłów powinien przejść do wartości zerowej, chyba że mają cykl, co oznacza, że wskazuje na węzeł główny.
Złożoność czasowa tego algorytmu jest,
O(n)
a złożoność przestrzeni jestO(1)
.Oto węzeł klasy dla listy połączonej:
Oto główny kod z prostym przypadkiem testowym trzech węzłów, które ostatni węzeł wskazuje na drugi węzeł:
Oto prosty przypadek testowy trzech węzłów, które ostatni węzeł wskazuje na drugi węzeł:
źródło
Ten kod jest zoptymalizowany i będzie generował wynik szybciej niż ten wybrany jako najlepsza odpowiedź. Ten kod pozwala uniknąć bardzo długiego procesu ścigania wskaźnika węzła do przodu i do tyłu, który nastąpi w następującym przypadku, jeśli zastosujemy się do „najlepszego” odpowiedz ”. Spójrz na suchą sekwencję poniższych, a zrozumiesz, co próbuję powiedzieć. Następnie spójrz na problem za pomocą podanej poniżej metody i zmierz nie. kroków podjętych w celu znalezienia odpowiedzi.
1-> 2-> 9-> 3 ^ -------- ^
Oto kod:
źródło
boolean hasLoop(Node first)
który zwróciłby wartość prawda, jeśli dany Węzeł jest pierwszą listą z pętlą, a fałsz w przeciwnym razie?Oto moje rozwiązanie w Javie
źródło
Możesz również użyć algorytmu żółwia Floyda, jak sugerowano w powyższych odpowiedziach.
Ten algorytm może sprawdzić, czy pojedynczo połączona lista ma zamknięty cykl. Można to osiągnąć przez iterację listy z dwoma wskaźnikami, które będą poruszać się z różną prędkością. W ten sposób, jeśli istnieje cykl, dwa wskaźniki spotkają się w pewnym momencie w przyszłości.
Zapraszam do zapoznania się z moim postem na blogu w strukturze danych list połączonych, w którym również zamieściłem fragment kodu z implementacją wyżej wspomnianego algorytmu w języku Java.
Pozdrowienia,
Andreas (@xnorcode)
źródło
Oto rozwiązanie do wykrywania cyklu.
źródło
// połączona lista funkcji wyszukiwania pętli
źródło
To podejście ma narzut miejsca, ale prostszą implementację:
Pętlę można zidentyfikować, przechowując węzły na mapie. I przed postawieniem węzła; sprawdź, czy węzeł już istnieje. Jeśli węzeł już istnieje na mapie, oznacza to, że lista połączona ma pętlę.
źródło
źródło