Bester Algorithmus zum Testen, ob eine verknüpfte Liste einen Zyklus hat

StackOverflow https://stackoverflow.com/questions/34249

Frage

Was ist der beste (Halte-)Algorithmus, um festzustellen, ob eine verknüpfte Liste einen Zyklus enthält?

[Bearbeiten] Eine Analyse der asymptotischen Komplexität sowohl für Zeit als auch für Raum wäre hilfreich, damit die Antworten besser verglichen werden können.

[Bearbeiten] Die ursprüngliche Frage bezog sich nicht auf Knoten mit einem Outdegree > 1, aber es gibt einige Diskussionen darüber.Diese Frage ähnelt eher „Bester Algorithmus zum Erkennen von Zyklen in einem gerichteten Graphen“.

War es hilfreich?

Lösung

Lassen Sie zwei Zeiger die Liste durchlaufen.Lassen Sie einen mit der doppelten Geschwindigkeit des anderen durchlaufen und vergleichen Sie ihre Positionen bei jedem Schritt.Spontan fällt mir so etwas ein wie:

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n), was so gut ist, wie es nur geht.

Andere Tipps

Voraussetzung:Behalten Sie die Listengröße im Auge (aktualisieren Sie die Größe, wenn ein Knoten hinzugefügt oder gelöscht wird).

Schleifenerkennung:

  1. Behalten Sie einen Zähler bei, wenn Sie die Listengröße durchlaufen.

  2. Wenn der Zähler die Listengröße überschreitet, liegt möglicherweise ein Zyklus vor.

Komplexität:An)

Notiz:Der Vergleich zwischen Zähler und Listengröße sowie der Aktualisierungsvorgang der Listengröße müssen threadsicher gemacht werden.

Nehmen Sie 2 Zeiger *p und *q und beginnen Sie mit dem Durchlaufen der verknüpften Liste „LL“ mit beiden Zeigern:

1) Zeiger p löscht jedes Mal den vorherigen Knoten und zeigt auf den nächsten Knoten.

2) Der Zeiger q bewegt sich jedes Mal nur in Vorwärtsrichtung.

Bedingungen:

1) Zeiger p zeigt auf Null und q zeigt auf einen Knoten:Schleife ist vorhanden

2) beide Zeiger zeigen auf null:es gibt keine Schleife

Wie wäre es mit der Verwendung einer Hash-Tabelle zum Speichern der bereits gesehenen Knoten (Sie betrachten sie in der Reihenfolge vom Anfang der Liste an)?In der Praxis könnten Sie etwas erreichen, das O(N) nahe kommt.

Andernfalls würde die Verwendung eines sortierten Heaps anstelle einer Hash-Tabelle O(N log(N)) erreichen.

Ich frage mich, ob es einen anderen Weg gibt, als einfach iterativ vorzugehen: Füllen Sie ein Array, während Sie vorwärts gehen, und prüfen Sie, ob der aktuelle Knoten bereits im Array vorhanden ist ...

Der Algorithmus von Konrad Rudolph funktioniert nicht, wenn der Zyklus nicht auf den Anfang zeigt.Die folgende Liste macht es zu einer Endlosschleife:1->2->3->2.

Der Algorithmus von DrPizza ist definitiv der richtige Weg.

In diesem Fall ist der Code von OysterD die schnellste Lösung (Scheitelpunktfärbung).

Das würde mich wirklich überraschen.Meine Lösung führt höchstens zwei Durchläufe durch die Liste durch (wenn der letzte Knoten mit dem vorletzten Knotenpunkt verknüpft ist) und führt im Normalfall (keine Schleife) nur einen Durchlauf durch.Ohne Hashing, ohne Speicherzuweisung usw.

In diesem Fall ist der Code von OysterD die schnellste Lösung (Scheitelpunktfärbung).

Das würde mich wirklich überraschen.Meine Lösung führt höchstens zwei Durchläufe durch die Liste durch (wenn der letzte Knoten mit dem vorletzten Knotenpunkt verknüpft ist) und führt im Normalfall (keine Schleife) nur einen Durchlauf durch.Ohne Hashing, ohne Speicherzuweisung usw.

Ja.Mir ist aufgefallen, dass die Formulierung nicht perfekt war, und habe sie umformuliert.Ich glaube immer noch, dass ein cleveres Hashing um Haaresbreite schneller sein könnte.Ich glaube deinem Algorithmus Ist aber die beste Lösung.

Nur um meinen Standpunkt zu unterstreichen:Die Vertec-Färbung wird von modernen Garbage Collectors zur Erkennung von Zyklen in Abhängigkeiten verwendet, es gibt also einen sehr realen Anwendungsfall dafür.Meistens verwenden sie Bit-Flags, um die Färbung durchzuführen.

Um dies festzustellen, müssen Sie jeden Knoten besuchen.Dies kann rekursiv erfolgen.Um zu verhindern, dass Sie bereits besuchte Knoten besuchen, benötigen Sie eine Markierung mit der Aufschrift „bereits besucht“.Dies führt natürlich nicht zu Schleifen.Verwenden Sie also anstelle eines Bit-Flags eine Zahl.Beginnen Sie bei 1.Überprüfen Sie die verbundenen Knoten, markieren Sie diese dann als 2 und führen Sie eine Rekursion durch, bis das Netzwerk abgedeckt ist.Wenn Sie beim Überprüfen von Knoten auf einen Knoten stoßen, der um mehr als eins kleiner als der aktuelle Knoten ist, liegt ein Zyklus vor.Die Zykluslänge ergibt sich aus der Differenz.

Am Kopf der Liste werden zwei Zeiger initialisiert.Ein Zeiger geht bei jedem Schritt einmal vorwärts, der andere bei jedem Schritt zweimal vorwärts.Trifft der schnellere Zeiger wieder auf den langsameren, entsteht eine Schleife in der Liste.Andernfalls gibt es keine Schleife, wenn der schnellere das Ende der Liste erreicht.

Der folgende Beispielcode wird gemäß dieser Lösung implementiert.Der schnellere Zeiger ist pFast und der langsamere ist 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;
}

Diese Lösung ist verfügbar unter mein Blog.Im Blog wird noch ein weiteres Problem besprochen:Was ist der Einstiegsknoten, wenn eine Liste einen Zyklus/eine Schleife enthält?

„Hack“-Lösung (sollte in C/C++ funktionieren):

  • Durchlaufen Sie die Liste und legen Sie das letzte Bit fest next Zeiger auf 1.
  • Wenn Sie ein Element mit einem markierten Zeiger finden, werden „true“ und das erste Element des Zyklus zurückgegeben.
  • Setzen Sie vor der Rückkehr die Zeiger zurück, obwohl ich glaube, dass die Dereferenzierung auch bei markierten Zeigern funktioniert.

Die Zeitkomplexität beträgt 2n.Es sieht so aus, als würden keine zeitlichen Variablen verwendet.

Dies ist eine Lösung, die eine Hash-Tabelle (eigentlich nur eine Liste) verwendet, um die Zeigeradresse zu speichern. 

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
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top