Erkennung einer Schleife in einer verketteten Liste ohne Algorithmus zur Erkennung von Floyd-Zyklen

Question

In einem Interview wurde ich gebeten, den Schleifenknoten in der verknüpften Liste zu ermitteln und die Anzahl der Knoten in der Schleife zu zählen. Da ich den Flyod-Algorithmus nicht kannte, versuchte ich, meinen eigenen Ansatz zu finden.

Die Idee ist in diesem Szenario, die Adresse von zwei Knoten wird auf den gleichen Knoten (Loop-Knoten) zeigen.

Eg.

1 -> 2 -> 4 -> 5 -> 7 -> 3 -> 4

Hier 2-> nächste und 3-> neben derselben, die die Adresse ist, von 4. Das bedeutet, dass es eine Schleife in der verketteten Liste gibt und 4 ist der Schleifenknoten. Und das Durchlaufen von 4 nach 4 ergibt die Anzahl der Knoten in der Schleife.

Gibt es eine Möglichkeit, dass wir mit diesem Ansatz fortfahren können ????

Answer 1

Natürlich können Sie einen Zyklus trivial finden, indem Sie eine Reihe von bereits besuchten Adressen beibehalten. Da Sie an der Schleifengröße interessiert sind, können Sie stattdessen eine Karte erstellen: address->count. Die Anzahl gibt an, wie viele Knoten beim Besuch des einen an der entsprechenden Adresse besucht wurden. Wenn Sie einen Knoten ermitteln, der bereits in der Tabelle enthalten ist, können Sie die Schleifengröße ermitteln, indem Sie die Anzahl in der Tabelle von der aktuellen abziehen. Natürlich können Sie den gleichen Effekt erzielen, indem Sie ein "besuchtes" Bit beibehalten und in den Knoten selbst zählen. Dann wird keine separate Karte benötigt.