Najlepszy algorytm do sprawdzenia, czy lista połączona ma cykl

Warunek wstępny: śledzenie rozmiaru listy (aktualizowanie rozmiaru po dodaniu lub usunięciu węzła).

Detekcja pętli:

1. Zachowaj licznik podczas przechodzenia przez rozmiar listy.

2. Jeśli licznik przekroczy rozmiar listy, możliwy jest cykl.

Złożoność: O (n)

Uwaga: porównanie licznika i rozmiaru listy, jak również operacja aktualizacji rozmiaru listy, muszą być bezpieczne dla wątku.

Weź dwa wskaźniki * p I * q, zacznij przemierzać połączoną listę " LL "używając obu wskaźników:

1) wskaźnik p usunie poprzedni węzeł za każdym razem i wskaże następny węzeł.

2) Wskaźnik q będzie poruszał się za każdym razem tylko w kierunku do przodu.

Warunki:

1) wskaźnik p wskazuje na null, a q wskazuje na jakiś węzeł: loop is present

2) oba wskaźniki wskazujące na null: nie ma pętli

A co z użyciem tabeli hash do przechowywania już widzianych węzłów (patrzysz na nie w kolejności od początku listy)? W praktyce można osiągnąć coś bliskiego O (N).

W przeciwnym razie, użycie posortowanej sterty zamiast tabeli hash uzyskałoby O (N log (N)).

Zastanawiam się, czy jest jakiś inny sposób niż po prostu iteracyjnie-wypełniaj tablicę, gdy robisz krok do przodu i sprawdź, czy bieżący węzeł jest już obecny w tablicy...

Algorytm Konrada Rudolfa nie zadziała, jeśli cykl nie wskazuje na początek. Poniższa lista uczyni ją nieskończoną pętlą: 1->2->3->2.

Algorytm Drpizzy jest zdecydowanie najlepszym rozwiązaniem.

W tym przypadku kod Osterda będzie najszybszym rozwiązaniem (kolorowanie wierzchołków)

W tym przypadku kod Osterda będzie najszybszym rozwiązaniem (kolorowanie wierzchołków)

To by mnie naprawdę zaskoczyło. Moje rozwiązanie wykonuje co najwyżej dwa przejścia przez Listę (jeśli ostatni węzeł jest połączony z przedostatnim lodem), a w powszechnym przypadku (brak pętli) zrobi tylko jedno przejście. Bez hashowania, bez alokacji pamięci itp.

Żeby podkreślić mój punkt widzenia: kolorowanie vertec jest używane do wykrywania cykli w zależności przez współczesnych śmieciarzy, więc istnieje bardzo realny przypadek użycia. Najczęściej używają bitowych FLAG do wykonywania kolorowania.

Będziesz musiał odwiedzić każdy węzeł, aby to określić. Można to zrobić rekurencyjnie. Aby zatrzymać odwiedzanie już odwiedzonych węzłów, potrzebujesz flagi z napisem "już odwiedzone". To oczywiście nie daje pętli. Więc zamiast flagi bitowej, użyj liczby. Zacznij od 1. Sprawdź połączone węzły, a następnie zaznacz je jako 2 i rekurencyjnie, dopóki sieć nie zostanie pokryta. Jeśli podczas sprawdzania węzłów napotkasz węzeł, który jest o więcej niż jeden mniejszy od bieżącego węzła, masz cykl. Długość cyklu jest podana przez różnicę.

Dwa wskaźniki są inicjowane na początku listy. Jeden wskaźnik do przodu raz na każdym kroku, a drugi do przodu dwa razy na każdym kroku. Jeśli szybszy wskaźnik spotka się ponownie z wolniejszym, na liście znajduje się pętla. W przeciwnym razie nie ma pętli, jeśli szybsza dotrze do końca listy.

Poniższy przykładowy kod jest zaimplementowany zgodnie z tym rozwiązaniem. Szybszy wskaźnik to pFast, a wolniejszy pSlow.

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

To rozwiązanie jest dostępne na mój blog . Jest kolejny problem omówiony na blogu: co to jest węzeł wejściowy, gdy na liście jest cykl / pętla?

Rozwiązanie"Hack "(powinno działać w C / C++):

• przemierzaj listę i ustaw ostatni bit wskaźnika next na 1.
• jeśli znajdziesz element z oznaczonym wskaźnikiem -- zwróć true i pierwszy element cyklu.
• Przed Powrotem zresetuj wskaźniki z powrotem, chociaż wierzę, że dereferencja będzie działać nawet z oznaczonymi wskaźnikami.

Złożoność czasu wynosi 2n. wygląda na to, że nie używa żadnych zmiennych czasowych.

Jest to rozwiązanie wykorzystujące tabelę skrótów (w rzeczywistości tylko listę) do zapisania adresu wskaźnika.

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

Def has_cycle(head): counter = set ()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next