Wie kann festgestellt werden, ob eine verkettete Liste eine Schleife enthält?

mögliche Dubletten:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle Wie kann festgestellt werden, ob eine verkettete Liste eine Schleife enthält?

Während einer Vorbereitung für ein Vorstellungsgespräch, stieß ich auf die folgende Frage:

Wie können Sie, ob eine Bestimmung verknüpfte Liste (beliebiger Art) enthält eine Schleife, die additio verwendet Raumkomplexität von O (1)? Sie können nicht davon ausgehen, dass die Schleife beim ersten Knoten beginnt (und natürlich muss die Schleife nicht alle Knoten enthalten).

ich die Antwort nicht finden konnte, obwohl ich das Gefühl, es ist ganz einfach haben ...

Quelle

2010-06-08 ET.

Ich habe diese genaue Frage in einem Interview selbst verpasst. Ich konnte nur die O (* n *) Speicher- und Zeitlösung geben. – Thanatos

Ich habe in einer CS-Klasse davon erfahren, aber ich denke nicht, dass es eine besonders gute Frage ist, da es "nur offensichtlich ist, wenn du es bereits weißt". –

Viele, viele Duplikate, z.B. [Finden Sie heraus, ob eine Schleife in einer verknüpften Liste ohne zwei Zeiger] (http://stackoverflow.com/questions/2338683/find-wether-a-loop-in-a-linked-list-without-towe-pointer) –

Einfach. Pflegen Sie zwei Zeiger in die Liste. Schieben Sie bei jedem Schritt einen Zeiger um eine einzelne Verbindung vor und schieben Sie die andere um zwei Verbindungen vor. Testen Sie, ob sie auf dasselbe Element zeigen. Wenn ja, hast du eine Schleife. Wenn nicht, wiederholen Sie den Vorgang, bis Sie eine Schleife gefunden haben oder Sie das Ende der Liste erreichen.

Quelle

2010-06-08 22:18:54 dty

+11

Ich fand, dass diese Lösung nur "einfach" war, wenn Sie es wussten. Das ist meiner Meinung nach ziemlich klug. – Thanatos

Interessant. Warum sollte man den anderen überhaupt voranbringen? –

Jeder Link kann mit jedem anderen Link übereinstimmen, daher müssen beide sich in der Liste bewegen, um jede (erreichbare) Kombination zu testen. – Ether

Wahrscheinlich die gleiche Technik wie die Überprüfung, ob ein Graph ein Baum ist (Bäume haben keine Zyklen), siehe this this question. Es wird entweder eine topologische Sortierung oder eine Tiefensuche empfohlen.

Quelle

2010-06-08 22:23:31 zdav

-1

Ich hatte letzte Woche genau dieses Problem im echten Live-Code.

Alles, was ich tat, war ein Zeiger (Link) für das erste Element gehalten. Dann, als ich die Liste durchging, wenn ich diesen Zeiger jemals wieder habe, weiß ich, dass es eine Schleife gibt.

Quelle

2010-06-08 22:38:52

Sehen Sie sich die Kommentare zu der akzeptierten Antwort an, warum das nicht alle * Zyklen erfasst, und warum dies eine bessere Lösung ist. –

Die Schleife beginnt nicht unbedingt beim ersten Element. –

Wie kann festgestellt werden, ob eine verkettete Liste eine Schleife enthält?

Antwort

Verwandte Themen