Wykryć pętlę na połączonej liście w C ++

Węzeł końcowy połączonej listy, która ma pętlę, będzie odnosić się do innego węzła na tej samej liście, a nie do null.Jeśli istnieje węzeł na połączonej liście, do którego można wielokrotnie dostępić, śledząc następny wskaźnik, mówi się, że lista ma cykl.

Zazwyczaj ostatni węzeł listy powiązanej odnosi się do zerowego odniesienia do oznaczenia wniosku listy. Jednak na połączonej liście z pętlą węzeł końcowy listy odnosi się do węzła startowego, węzła wewnętrznego lub samego siebie. Dlatego w takich okolicznościach musimy zidentyfikować i zakończyć pętlę, ustawiając odniesienie następnego węzła do NULL. Część wykrywalności pętli na połączonej liście jest wyjaśniona w tym artykule.

W C ++ istnieje wiele sposobów na znalezienie pętli na połączonej liście:

Podejście oparte na tabeli HASH: To podejście przechowuje adresy odwiedzonych węzłów w tabeli skrótów. Pętla na połączonej liście istnieje, jeśli węzeł jest już obecny w tabeli skrótów, gdy zostanie ponownie odwiedzony.

Podejście rowerowe Floyda: Algorytm „żółwia i zająca”, powszechnie znany jako algorytm ustalania cyklu Floyda: ta technika wykorzystuje dwa wskaźniki, jeden poruszający się wolniej niż drugi, a drugi porusza się szybciej. Szybszy wskaźnik ostatecznie wyprzedzi wolniejszy wskaźnik, jeśli istnieje pętla na połączonej liście, ujawniając istnienie pętli.

Metoda rekurencyjna: Ta metoda przechodzi przez linkowaną listę, wzywając się w kółko. Połączona lista zawiera pętlę, jeśli obecny węzeł został wcześniej odwiedzany.

Podejście oparte na stosie: To podejście przechowuje adresy odwiedzonych węzłów w stosie. Pętla na listy połączonej jest obecna, jeśli węzeł jest już na stosie, gdy zostanie ponownie odwiedzony.

Wyjaśnijmy każde podejście szczegółowo, aby zrozumieć koncepcję.

Podejście 1: Podejście do hashset

Wykorzystanie mieszania jest najprostszą metodą. Tutaj przechodzimy listę jeden po drugim, zachowując tabelę skrótów z adresami węzłów. Dlatego pętla istnieje, jeśli kiedykolwiek przebiegniemy na następny adres obecnego węzła, który jest już zawarty w tabeli skrótów. W przeciwnym razie nie ma pętli na listy powiązanej, jeśli wpadniemy na NULL (i.mi., Dotrzyj na koniec linkowanej listy).

Wdrożenie tej strategii będzie dość łatwe.

Podczas przemierzania listy połączonej, skorzystamy z UNOPOREDED_HASHMAP i nadal dodajemy do niej węzły.

Teraz, gdy natkniemy się na węzeł, który jest już pokazany na mapie, będziemy wiedzieć, że dotarliśmy na początek pętli.

• • Ponadto na każdym kroku trzymaliśmy dwa wskaźniki, HEADNODE wskazując na bieżący węzeł i LastNode wskazując na poprzedni węzeł bieżącego węzła, podczas iteracji.
  • Jak nasz HEADNODE teraz wskazuje na węzeł początkowy pętli i jako LastNode wskazywał na węzeł, na który wskazywała głowa (i.mi., odnosi się do LastNode pętli), nasz HEADNODE Obecnie wskazuje na węzeł początkowy pętli.
  • Pętla zostanie zepsuta przez ustawienie Lastnode-> następny == null.

W ten sposób węzeł końcowy pętli zamiast odnosić się do początkowego węzła pętli, zaczyna wskazywać na NULL.

Średni czas i złożoność przestrzeni metody mieszania wynosi O (N). Czytelnik powinien zawsze mieć świadomość, że wdrożenie wbudowanej danych ze mieszania w języku programowania określi całkowitą złożoność czasu w przypadku kolizji w haszku.

Implementacja programu C ++ dla powyższej metody (Hashset):

#włączać
za pomocą przestrzeni nazw Std;
Node struct
wartość int;
Node struct* następny;
;
Węzeł* newNode (wartość int)

Węzeł* tempnode = nowy węzeł;
tempNode-> wartość = wartość;
tempnode-> następny = null;
return TempNode;

// Zidentyfikuj i wyeliminuj wszelkie potencjalne pętle
// na połączonej liście z tą funkcją.
void funkcjaHashmap (węzeł* headnode)

// utworzył UNOPORDED_MAP, aby zaimplementować mapę skrótu
UNOPORDED_MAP hash_map;
// wskaźnik do ostatniego
Węzeł* lastNode = null;
When (Headnode != Null)
// Jeśli na mapie brakuje węzła, dodaj go.
if (hash_map.Znajdź (headnode) == HASH_MAP.koniec())
hash_map [headnode] ++;
lastNode = HeadNode;
HeadNode = HeadNode-> następny;

// Jeśli cykl jest obecny, ustaw następny wskaźnik węzła końcowego na NULL.
w przeciwnym razie
lastNode-> następny = null;
przerwa;



// Wyświetl listę połączoną
Display void (węzeł* headnode)

When (Headnode != Null)
Cout HeadNode = HeadNode-> następny;

Cout << endl;

/* Główna funkcja*/
int main ()

Węzeł* headNode = newNode (48);
HeadNode-> następny = headNode;
HeadNode-> Next = NewNode (18);
HeadNode-> następny-> następny = newNode (13);
HeadNode-> następny-> następny-> następny = newNode (2);
HeadNode-> następny-> następny-> następny-> następny = newNode (8);
/ * Utwórz pętlę w LinkedList */
HeadNode-> następny-> następny-> następny-> następny-> następny = HeadNode-> następny-> następny;
funkcjahashmap (headNode);
printf („Lista linkowana bez pętli \ n”);
wyświetlacz (headnode);
powrót 0;

Wyjście:

Połączona lista bez pętli
48 18 13 2 8

Wyjaśnienie kodu krok po kroku podano poniżej:

1. 1. Bity/stdc++.H> plik nagłówka, który zawiera wszystkie wspólne biblioteki C ++, jest zawarty w kodzie.
   2. Konstruowana jest struktura o nazwie „węzeł” i ma dwa elementy: odniesienie do następnego węzła na liście i liczbę całkowitą o nazwie „Wartość."
   3. Z wartością całkowitą jako wejściową i „następnym” wskaźnikiem ustawionym na NULL, funkcja „newNode” tworzy nowy węzeł z tą wartością.
   4. Funkcja 'funkcjaHashmap ' jest zdefiniowane, co przenosi wskaźnik do węzła głównego listy połączonej jako wejście.
   5. W środku 'funkcjahashmap„Funkcja, utworzona jest UNOREDRED_MAP„ HASH_MAP ”, która służy do wdrożenia struktury danych mapy skrótu.
   6. Wskaźnik do ostatniego węzła listy jest inicjowany do null.
   7. Pętla while jest używana do przemierzania listy połączonej, która zaczyna się od węzła głównego i trwa do momentu, gdy węzeł głowy nie będzie null.
   8. Wskaźnik LastNode jest aktualizowany do bieżącego węzła wewnątrz pętli while, jeśli bieżący węzeł (headnode) nie jest jeszcze obecny na mapie skrótu.
   9. Jeśli bieżący węzeł zostanie znaleziony na mapie, oznacza to, że pętla jest obecna na listy połączonej. Aby usunąć pętlę, następny wskaźnik LastNode jest ustawione na ZERO a pętla, w którym pęka jest złamana.
   10. Węzeł główny listy połączonej jest używany jako wejście dla funkcji o nazwie „Wyświetl”, która wyświetla wartość każdego węzła na liście od początku do końca.
   11. w główny funkcja, tworzenie pętli.
   12. Funkcja „funkcjahashmap” jest wywoływana z wskaźnikiem nodowym jako wejście, co usuwa pętlę z listy.
   13. Zmodyfikowana lista jest wyświetlana za pomocą funkcji „wyświetlanie”.

Podejście 2: Cykl Floyda

Algorytm wykrywania cyklu Floyda, często znany jako algorytm żółwia i zając, stanowi podstawę tej metody lokalizacji cykli na połączonej liście. „Wolny” wskaźnik i „szybki” wskaźnik, który przemierzają listę przy różnych prędkościach, to dwa wskaźniki używane w tej technice. Szybki wskaźnik rozwija dwa kroki, podczas gdy powolny wskaźnik rozwija jeden krok w każdej iteracji. Cykl na połączonej liście istnieje, jeśli dwa punkty kiedykolwiek pojawią się twarzą w twarz.

1. Z węzłem głównym listy powiązanej zainicjujemy dwa wskaźniki o nazwie Fast and Slow.

2. Teraz uruchamiamy pętlę, aby przejść przez połączoną listę. Szybki wskaźnik powinien zostać przeniesiony do dwóch lokalizacji przed powolnym wskaźnikiem na etapie każdej iteracji.

3. Nie będzie pętli na połączonej liście, jeśli szybki wskaźnik osiągnie koniec listy (fastPointer == null lub fastPointer-> następny == null). Jeśli nie, szybkie i powolne wskaźniki ostatecznie się spełnią, co oznacza, że ​​powiązana lista ma pętlę.

Implementacja programu C ++ dla powyższej metody (cykl Floyda):

#włączać
za pomocą przestrzeni nazw Std;
/ * Węzeł listy linków */
Node struct
dane int;
Node struct* następny;
;
/* Funkcja usuwania pętli. */
void DeleTeLoop (node ​​struct*, struct node*);
/* Ta funkcja lokalizuje i eliminuje pętle list. Daje 1
Jeśli na liście była pętla; w przeciwnym razie zwraca 0. */
Int DetectandDeleTeLoop (lista węzłów struct))

struct node *lista slowptr =, *fastptr = lista;
// iteruj, aby sprawdzić, czy pętla jest tam.
while (slowptr && fastptr && fastptr-> następny)
SULLPTR = SULLPTR-> następny;
fastPtr = fastPtr-> następny-> następny;
/* Jeśli w pewnym momencie spotykają się powolne i fastptr
jest pętlą */
if (slowptr == fastptr)
DeleTeLoop (Slowptr, List);
/* Zwróć 1, aby wskazać, że wykryto pętlę. */
zwrot 1;


/* Zwróć 0, aby wskazać, że nie odkryto żadnej pętli.*/
powrót 0;

/* Funkcja usuwania pętli z listy połączonej.
Loopnode wskazuje na jeden z węzłów pętli, a wskazuje
do węzła początkowego linkowanej listy */
void DeleTeLoop (Node struct LOOPNODE, Node struct* HeadNode)

struct node* ptr1 = loopnode;
struct node* ptr2 = loopnode;
// Policz, ile węzłów jest w pętli.
niepodpisany int k = 1, i;
podczas gdy (ptr1-> następny != ptr2)
ptr1 = ptr1-> następny;
K ++;

// Napraw jeden wskaźnik do headnode
ptr1 = headnode;
// i drugi wskaźnik do k węzłów po headnode
ptr2 = headnode;
dla (i = 0; i < k; i++)
ptr2 = ptr2-> następny;
/* Gdy oba punkty są przenoszone jednocześnie,
zderzyją się w początkowym węźle pętli. */
podczas gdy (ptr2 != ptr1)
ptr1 = ptr1-> następny;
ptr2 = ptr2-> następny;

// Uzyskaj ostatni wskaźnik węzła.
While (ptr2-> następny != ptr1)
ptr2 = ptr2-> następny;
/* Aby zamknąć pętlę, ustaw kolejne
węzeł do węzła kończącego pętlę. */
ptr2-> następny = null;

/ * Funkcja wyświetlania połączonej listy */
void displayLinkedList (węzeł struct*)

// Wyświetl linkowaną listę po usunięciu pętli
While (węzeł != Null)
Cout node = węzeł-> następny;


Node struct* newNode (klucz int)

struct node* temp = new node ();
temp-> data = klucz;
temp-> następny = null;
Return Temp;

// Kod główny
int main ()

struct node* headNode = newNode (48);
HeadNode-> Next = NewNode (18);
HeadNode-> następny-> następny = newNode (13);
HeadNode-> następny-> następny-> następny = newNode (2);
HeadNode-> następny-> następny-> następny-> następny = newNode (8);
/ * Utwórz pętlę */
HeadNode-> następny-> następny-> następny-> następny-> następny = HeadNode-> następny-> następny;
// Wyświetl pętlę na listy połączonej
// displayLinkedList (headNode);
detectandDeleTeLoop (headnode);
Cout << "Linked List after no loop \n";
displayLinkedList (HeadNode);
powrót 0;

Wyjście:

Połączona lista po braku pętli
48 18 13 2 8

Wyjaśnienie:

1. 1. Odpowiednie nagłówki, takie jak „BIT/STDC++.H ”i„ STD :: Cout ”są po raz pierwszy.
   2. Następnie zadeklarowana jest struktura „węzła”, która oznacza węzeł na połączonej liście. Kolejny wskaźnik, który prowadzi do następującego węzła na liście, jest uwzględniony wraz z polem danych liczb całkowitych w każdym węźle.
   3. Następnie definiuje „DeletEloop” i „DetectandDeleTeLoop”, dwie funkcje. Pętla jest usuwana z połączonej listy przy użyciu pierwszej metody, a pętla jest wykrywana na liście za pomocą drugiej funkcji, która następnie wywołuje pierwszą procedurę usuwania pętli.
   4. W głównej funkcji powstaje nowa lista z pięcioma węzłami, a pętla jest ustalana przez ustawienie następnego wskaźnika ostatniego węzła na trzeci węzeł.
   5. Następnie wywołuje metodę „detectandDeleteluoop” podczas przekazywania węzła głównego listy powiązanej jako argumentu. Aby zidentyfikować pętle, ta funkcja wykorzystuje podejście „powolne i szybkie wskaźniki”. Wykorzystuje dwa wskaźniki, które zaczynają się na szczycie listy, Slowptr i FastPtr. Podczas gdy szybki wskaźnik porusza dwa węzły jednocześnie, powolny wskaźnik porusza tylko jeden węzeł na raz. Szybki wskaźnik ostatecznie wyprzedzi powolny wskaźnik, jeśli lista zawiera pętlę, a dwa punkty zderzy się w tym samym węźle.
   6. Funkcja wywołuje funkcję „DeleTeLoop”, jeśli znajdzie pętlę, dostarczając węzeł główny listy oraz przecięcie powolnych i szybkich wskaźników jako wejścia. Ta procedura ustanawia dwa wskaźniki, PTR1 i PTR2, do węzła głównego listy i liczy liczbę węzłów w pętli. Następnie rozwija jeden wskaźnik K, gdzie K jest całkowitą liczbą węzłów w pętli. Następnie, dopóki nie spotkają się na początku pętli, rozwija się oba punkty jeden węzeł na raz. Pętla jest następnie rozbijana przez ustawienie następnego wskaźnika węzła na końcu pętli na null.
   7. Po usunięciu pętli wyświetla połączoną listę jako ostatni krok.

Podejście 3: Rekurencja

Rekursiona jest techniką rozwiązywania problemów poprzez podzielenie ich na mniejsze, łatwiejsze podproblemy. Rekurencja może być używana do przemierzania pojedynczo połączonej listy w przypadku, gdy pętla jest wykonywana przez ciągłe uruchamianie funkcji dla następnego węzła na liście, aż do osiągnięcia końca listy.

Na pojedynczo połączonej liście podstawową zasadą za pomocą Recursion w celu znalezienia pętli jest rozpoczęcie na czele listy, zaznacz bieżący węzeł odwiedzany na każdym kroku, a następnie przejdź do następnego węzła, rekursywnie wywołując funkcję dla funkcji dla ten węzeł. Metoda będzie iterowana w pełnej listy połączonej, ponieważ nazywa się ją rekurencyjnie.

Lista zawiera pętlę, jeśli węzeł, który był wcześniej oznaczony jako odwiedzany, jest napotkany przez funkcję; W takim przypadku funkcja może zwrócić prawdziwe. Metoda może zwrócić false, jeśli osiągnie koniec listy bez biegania przez odwiedzony węzeł, co wskazuje, że nie ma pętli.

Chociaż ta technika wykorzystywania rekurencji do znalezienia pętli na jednej połączonej liście jest prosta w użyciu i zrozumieniu, może nie być najskuteczniejsza pod względem złożoności czasu i przestrzeni.

Wdrożenie programu C ++ dla powyższej metody (Recursion):

#włączać
za pomocą przestrzeni nazw Std;
Node struct
dane int;
Węzeł* następny;
Bool odwiedził;
;
// Funkcja wykrywania pętli powiązanej
Bool detectLoopLinkedList (węzeł* headnode)
if (headnode == null)
zwrócić fałsz; // Jeśli lista połączona jest pusta, podstawowy przypadek

// istnieje pętla, jeśli ma bieżący węzeł
// już odwiedzano.
if (headnode-> odwiedzone)
zwrócić true;

// Dodaj znak wizyty do bieżącego węzła.
HeadNode-> odwiedzone = true;
// wywoływanie kodu dla kolejnego węzła wielokrotnie
return detectLoopLinkedList (HeadNode-> następny);

int main ()
Node* headNode = new node ();
Węzeł* secondNode = new node ();
Węzeł* trzecinode = nowy node ();
HeadNode-> data = 1;
HeadNode-> następny = secondNode;
HeadNode-> odwiedzone = false;
secondNode-> data = 2;
secondNode-> następny = trzecinode;
secondNode-> odwiedzone = false;
trzecinode-> data = 3;
trzecinode-> next = null; // Brak pętli
trzecinode-> odwiedzony = false;
if (detectLoopLinkedList (headNode))
Cout << "Loop detected in linked list" << endl;
w przeciwnym razie
Cout << "No loop detected in linked list" << endl;

// Tworzenie pętli
trzecinode-> następny = secondNode;
if (detectLoopLinkedList (headNode))
Cout << "Loop detected in linked list" << endl;
w przeciwnym razie
Cout << "No loop detected in linked list" << endl;

powrót 0;

Wyjście:

Brak pętli wykrytych na powiązanej liście
Pętla wykryta na powiązanej liście

Wyjaśnienie:

1. 1. Funkcja detectLooplinkedList () W tym programie akceptuje szef linkowanej listy jako dane wejściowe.
   2. Rekurencja jest używana przez funkcję do iteracji w połączonej liście. Jako podstawowy przypadek rekurencji, zaczyna się od ustalenia, czy bieżący węzeł jest zerowy. Jeśli tak, metoda zwraca false, wskazując, że żadna pętla nie istnieje.
   3. Wartość właściwości „odwiedzonej” bieżącego węzła jest następnie sprawdzana, czy została wcześniej odwiedzana. Powraca prawdą, jeśli został odwiedzony, sugerując, że znaleziono pętlę.
   4. Funkcja oznacza obecny węzeł, który odwiedzono, jeśli został już odwiedzony przez zmianę jego „odwiedzonej” na prawdziwie.
   5. Wartość odwiedzonej zmiennej jest następnie sprawdzana, czy obecny węzeł został wcześniej odwiedzany. Jeśli był używany wcześniej, musi istnieć pętla, a funkcja zwraca się prawdziwie.
   6. Wreszcie funkcja wywołuje następny węzeł na liście, przechodząc HeadNode-> Dalej jako argument. Rekurencyjnie, Jest to przeprowadzane do momentu znalezienia pętli lub odwiedzonych wszystkich węzłów. Oznacza, że ​​funkcja ustawia zmienną zmienną na true, jeśli bieżący węzeł nigdy nie został odwiedzony przed rekurencyjnym wezwaniem do następującego węzła na listy połączonej.
   7. Kod buduje trzy węzły i dołącza do nich, aby stworzyć połączoną listę w główna funkcja. Metoda detectLooplinkedList () Następnie jest wywoływany w węźle głównym listy. Program produkuje „Odliczona pętla na listy powiązanych" Jeśli detectLooplinkedList () zwraca prawdziwie; W przeciwnym razie wysyła „Brak pętli wykrytych na powiązanej liście".
   8. Następnie kod wprowadza pętlę do linkowanej listy, ustawiając następny wskaźnik ostatniego węzła do drugiego węzła. Następnie, w zależności od wyniku funkcji, działa detectLooplinkedList () znowu i produkuje albo „Odliczona pętla na listy powiązanych" Lub "Brak pętli wykrytych na powiązanej liście."

Podejście 4: Korzystanie z stosu

Pętle na połączonej liście można znaleźć za pomocą stosu i metody „Wyszukiwarka głębokości” (DFS). Podstawową koncepcją jest iteracja za pośrednictwem listy powiązanej, wciskając każdy węzeł na stos, jeśli jeszcze go nie odwiedzono. Pętla jest rozpoznawana, jeśli węzeł, który jest już na stosie.

Oto krótki opis procedury:

1. 1. Utwórz pusty stos i zmienną do rejestrowania odwiedzanych węzłów.
   2. Wciśnij połączoną listę na stos, zaczynając od góry. Zwróć uwagę, że głowa została odwiedzona.
   3. Wepchnij następny węzeł na liście na stos. Dodaj znak wizyty do tego węzła.
   4. Podczas przecinania listy wciśnij każdy nowy węzeł na stos, aby wskazać, że został odwiedzony.
   5. Sprawdź, czy węzeł, który był wcześniej odwiedzany, znajduje się na górze stosu. Jeśli tak, znaleziono pętlę, a pętla jest identyfikowana przez węzły w stosie.
   6. Wyprowadź węzły ze stosu i przemierzaj listę, jeśli nie znaleziono pętli.

Implementacja programu C ++ dla powyższej metody (stos)

#włączać
#włączać
za pomocą przestrzeni nazw Std;
Node struct
dane int;
Węzeł* następny;
;
// funkcja wykrywania pętli na połączonej liście
Bool detectLoopLinkedList (węzeł* headnode)
stos stos;
Węzeł* tempnode = headNode;
While (tempnode != Null)
// Jeśli górny element stosu pasuje
// bieżący węzeł i stos nie jest pusty
Jeśli (!stos.pusty () && Stack.top () == tempnode)
zwrócić true;

stos.push (tempnode);
tempNode = tempnode-> następny;

zwrócić fałsz;

int main ()
Node* headNode = new node ();
Węzeł* secondNode = new node ();
Węzeł* trzecinode = nowy node ();
HeadNode-> data = 1;
HeadNode-> następny = secondNode;
secondNode-> data = 2;
secondNode-> następny = trzecinode;
trzecinode-> data = 3;
trzecinode-> next = null; // Brak pętli
if (detectLoopLinkedList (headNode))
Cout << "Loop detected in linked list" << endl;
w przeciwnym razie
Cout << "No loop detected in linked list" << endl;

// Tworzenie pętli
trzecinode-> następny = secondNode;
if (detectLoopLinkedList (headNode))
Cout << "Loop detected in linked list" << endl;
w przeciwnym razie
Cout << "No loop detected in linked list" << endl;

Wyjście:

Brak pętli wykrytych na powiązanej liście
Pętla wykryta na powiązanej liście

Wyjaśnienie:

Ten program używa stosu, aby dowiedzieć się, czy pojedynczo połączona lista ma pętlę.

• 1. Biblioteka strumienia wejściowego/wyjściowego i biblioteka stosu są obecne w pierwszym wierszu.

  2. Standardowa przestrzeń nazw jest zawarta w drugim wierszu, co pozwala nam uzyskać dostęp do funkcji biblioteki strumienia wejściowego/wyjściowego bez konieczności prefiksowania ich za pomocą „STD ::."

  3. Poniższy wiersz określa węzeł struktury, który składa się z dwóch członków: liczby całkowitej zwanej „danymi” i wskaźnika do innego węzła o nazwie „Dalej."

  4. Głowa listy połączonej jest wejściem dla metody detectLoopLinkedList (), która jest zdefiniowana w następnym wierszu. Funkcja wytwarza wartość logiczną, która wskazuje, czy znaleziono pętlę.

  5. Stos wskaźników węzłów zwanych „stosem” i wskaźnik do węzła o nazwie „Tempnode”, który jest inicjowany z wartością nody.

  6. Wtedy, dopóki TempNode nie jest wskaźnikiem zerowym, wchodzimy w pętlę.

  (a) Górny element stosu musi pasować do bieżącego węzła, abyśmy mogli ustalić, że nie jest on pusty. Zwracamy prawdę, jeśli tak jest, ponieważ znaleziono pętlę.

  (b) Jeśli wyżej wymieniony warunek jest fałszywy, bieżący wskaźnik węzła jest wciśnięty na stos, a tempNode jest ustawiony na następujący węzeł na listy połączonej.

  7. Wracamy fałsz po pętli, ponieważ nie zaobserwowano pętli.

  8. Budujemy trzy obiekty węzłów i inicjujemy je w funkcji Main (. Ponieważ w pierwszym przykładzie nie ma pętli, prawidłowo ustawiamy wskazówki „następne”.

Wniosek:

Podsumowując, najlepsza metoda wykrywania pętli na połączonej liście zależy od konkretnego przypadku użycia i ograniczeń problemu. Tabela hash i algorytm cyklu Floyda są wydajnymi metodami i są szeroko stosowane w praktyce. Stos i rekurencja są mniej wydajnymi metodami, ale są bardziej intuicyjne.