Die meisten Lösungen zum Erkennen der Schleife in einer verketteten Liste sagen, dass der schnelle Zeiger zweimal die Schritte des langsamen Zeigers verschieben muss. Warum können wir nicht den schnellen Zeiger nur einen Schritt voraus haben und wenn fast.next == slow
wir fertig sind. Der Code würde wie folgtWarum muss der schnelle Zeiger in der Schleifenerkennung der verknüpften Liste zwei Schritte voraus sein?
slow = head;
fast = head.next;
while(fast.next != slow)
{
slow = slow.next;
fast = fast.next;
if(fast == null) /* No loop to begin with, break */
break;
}
return fast; /* The starting loop node*/
Edits aussehen: Ich meinte fast.next = langsam
Ihn, wie würde das Zyklus größeren Länge tha erfassen n, wie, 2? –
Was bedeutet das? Dieser Ansatz mag naiv sein, aber es sollte funktionieren. Das Fasten ist immer eins voraus. hier treffen sich schnell und langsam nicht aber langsam.next muss für einen Zyklus gleich schnell sein. – Hooli
Äh, wie es aussieht, ist "langsam.next" immer gleich "schnell", egal ob es einen Zyklus gibt oder nicht. Zu sagen "das schnelle ist immer eins voraus" ist dasselbe wie zu sagen "langsam.next ist gleich schnell". –