Zyklus in verknüpfter Liste erkennen

Ein weiterer Algorithmus für verknüpfte Listen.

Erkennen Sie einen Zyklus in einer verknüpften Liste.

Das ist eigentlich gar nicht so schlimm. Es gibt mindestens drei verschiedene Möglichkeiten, dies O(n)-mal zu tun.

Der einfachste Weg besteht darin, den Knoten der verknüpften Liste so zu ändern, dass er ein Flag enthält, das angibt, ob ein Knoten besucht wurde. Wenn wir beim Durchlaufen der Liste auf einen Knoten stoßen, der besucht wurde, gibt es einen Zyklus.

Eine andere Technik verwendet eine Hashmap, die besuchte Knoten oder Verweise darauf enthält. Beim Durchlaufen der Liste werden Knoten oder ihre Referenzen in den Hash eingefügt. Wenn wir auf einen Knoten stoßen, der bereits in der Hashmap dargestellt ist, liegt ein Zyklus vor. Während diese Technik nur einen einzigen Durchlauf erfordert, benötigt sie aufgrund der Hashmap mehr Speicher.

Für diesen Beitrag werde ich Floyds Algorithmus verwenden, um den Zyklus zu erkennen. Es ist ziemlich einfach.

func DetectCycle[T any](ll *LinkedList[T]) bool {
    slow := ll.Head
    fast := ll.Head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            return true
        }
    }
    return false
}

Diese Technik verwendet 2 Zeiger in die Liste. Beim Durchlaufen der Liste bewegt ein Zeiger jeweils einen Knoten und der andere jeweils zwei Knoten. Wenn sich die beiden Zeiger jemals treffen, liegt ein Zyklus vor.

Warum funktioniert das? Beim Durchlaufen der Liste vergrößert sich der Abstand zwischen den beiden Zeigern. Wenn es einen Zyklus gibt, „rundet“ der schnelle Zeiger den langsamen.

Gibt es eine effizientere Umsetzung? Fehlen Randbedingungen? Lass es mich in den Kommentaren wissen.

Danke!

Den Code für diesen Beitrag und alle Beiträge dieser Reihe finden Sie hier

Das obige ist der detaillierte Inhalt vonZyklus in verknüpfter Liste erkennen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!