Lösung 1 - mit freundlicher Genehmigung von Career Cup und Buch "Cracking the Coding Interview". :
public static LinkedListNode findStartOfLoop(LinkedListNode head) {
LinkedListNode n1 = head;
LinkedListNode n2 = head;
// find meeting point using Tortoise and Hare algorithm
// this is just Floyd's cycle detection algorithm
while (n2.next != null) {
n1 = n1.next;
n2 = n2.next.next;
if (n1 == n2) {
break;
}
}
// Error check - there is no meeting point, and therefore no loop
if (n2.next == null) {
return null;
}
/* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps
/* from the Loop Start. If they move at the same pace, they must
* meet at Loop Start. */
n1 = head;
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
// Now n2 points to the start of the loop.
return n2;
}
Die Erklärung für diese Lösung ist direkt aus dem Buch:
Wenn wir zwei Zeiger verschieben, einen mit Geschwindigkeit 1 und einem anderen mit Geschwindigkeit 2, werden sie sich am Ende treffen, wenn die verknüpfte Liste eine Schleife hat. Und warum? Denken Sie an zwei Autos, die auf einer Strecke fahren; das schnellere Auto wird immer das langsamere überholen!
Der knifflige Teil besteht darin, den Anfang zu finden der Schleife zu finden. Stellen Sie sich, als Analogie, vor zwei Personen rennen um eine Bahn, einer läuft doppelt so schnell wie der andere. Wenn sie an der gleichen Stelle starten wann werden sie sich das nächste Mal treffen? Sie treffen sich beim Start der nächsten nächsten Runde.
Nehmen wir nun an, Fast Runner hätte einen Vorsprung von k Metern auf einer Runde mit n Schritten. Wann werden sie sich das nächste Mal treffen? Sie treffen sich k Meter vor dem Start der nächsten Runde. (Warum? Fast Der Läufer hätte k + 2(n - k) Schritte gemacht, einschließlich seines Vorsprungs, und der langsame Läufer hätte n - k Schritte gemacht Beide werden k Schritte vor dem Start der Schleife).
Nun zurück zum Problem: Wenn Fast Runner (n2) und Slow Runner (n1) sich um unseren kreisförmig verknüpften Liste bewegen, hat n2 einen Vorsprung in der Schleife, wenn n1 eintritt. Genauer gesagt, hat er einen Vorsprung von k, wobei k die Anzahl der der Knoten vor der Schleife ist. Da n2 einen einen Vorsprung von k Knoten hat, werden n1 und n2 k Knoten vor dem Beginn der Schleife treffen der Schleife.
Wir wissen jetzt also Folgendes:
- Kopf ist k Knoten vom LoopStart entfernt (per Definition)
- MeetingPoint für n1 und n2 ist k Knoten von LoopStart (wie oben gezeigt)
Wenn wir also n1 zurück nach Head bewegen und n2 am MeetingPoint belassen und beide im gleichen Tempo bewegen, werden sie sich am LoopStart treffen
Lösung 2 - mit freundlicher Genehmigung von mir :)
public static LinkedListNode findHeadOfLoop(LinkedListNode head) {
int indexer = 0;
Map<LinkedListNode, Integer> map = new IdentityHashMap<LinkedListNode, Integer>();
map.put(head, indexer);
indexer++;
// start walking along the list while putting each node in the HashMap
// if we come to a node that is already in the list,
// then that node is the start of the cycle
LinkedListNode curr = head;
while (curr != null) {
if (map.containsKey(curr.next)) {
curr = curr.next;
break;
}
curr = curr.next;
map.put(curr, indexer);
indexer++;
}
return curr;
}
Ich hoffe, das hilft.
Hristo
