Erstellen Sie eine Duplikatkopie der verketteten Liste in O(n) Zeit

Question

Eine Verknüpfungsliste wird mit zwei Zeigern angegeben, der erste zeigt auf den nächsten Knoten und der andere zeigt auf einen zufälligen Zeiger. Der Zufallszeiger zeigt auf einen beliebigen Knoten der Verknüpfungsliste. Schreiben Sie ein vollständiges Programm zum Erstellen einer Kopie der Verknüpfungsliste (c, c ++, c#), ohne die ursprüngliche Liste zu ändern und in O(n).

Ich wurde in einem der Interviews nach dieser Frage gefragt und konnte die Lösung nicht herausfinden. Hilfe würde geschätzt werden.

Answer 1

Das Kopieren einer normalen verketteten Liste in linearer Zeit ist offensichtlich trivial. Der einzige Teil, der dies interessant macht, ist der "zufällige" Zeiger. Vermutlich meinen Sie mit "zufällig" wirklich, dass er auf einen anderen zufällig gewählten Knoten in derselben verketteten Liste zeigt. Vermutlich soll die Kopie der verketteten Liste genau dieselbe Struktur wiederherstellen - d.h., die 'next'-Zeiger erstellen eine lineare Liste, und die anderen Zeiger verweisen auf dieselben relativen Knoten (zum Beispiel, wenn der zufällige Zeiger im ersten Knoten der Originalliste auf den fünften Knoten in der Originalliste zeigte, dann würde der zufällige Zeiger in der Duplikatliste auch auf den fünften Knoten der Duplikatliste zeigen.

Das in N2-Zeit zu machen, ist ziemlich einfach. Zunächst wird die Liste normal dupliziert, wobei der zufällige Zeiger ignoriert wird. Dann gehen Sie durch die Originalliste einen Knoten nach dem anderen und gehen für jeden Knoten erneut durch die Liste, um herauszufinden, auf welchen Knoten der Liste der zufällige Zeiger verwies (d.h., wie viele Knoten Sie über die next-Zeiger durchlaufen müssen, um einen next-Zeiger zu finden, der dieselbe Adresse wie der random-Zeiger des aktuellen Knotens enthält. Dann durchlaufen Sie die Duplikatliste und stellen das umgekehrt dar - finden Sie die Adresse des Nten Knotens und setzen Sie das in den zufälligen Zeiger des aktuellen Knotens.

Der Grund, warum dies O(N2) ist, sind hauptsächlich diese linearen Suchen nach den richtigen Knoten. Um O(N) zu erreichen, müssen diese Suchen mit konstanter Komplexität anstelle von linearer Komplexität durchgeführt werden.

Der offensichtliche Weg, dies zu tun, wäre der Aufbau einer Hashtabelle, die die Adresse jedes Knotens in der Originalliste auf die Position dieses Knotens in der Liste abbildet. Dann können wir ein Array erstellen, das die Adressen der Knoten in der neuen Liste enthält.

Mit diesen ist es ziemlich einfach, die zufälligen Zeiger zu reparieren. Zuerst gehen wir durch die Originalliste über die next-Zeiger, duplizieren die Knoten und bauen unsere neue Liste über die next-Zeiger verbunden auf, lassen aber die zufälligen Zeiger unverändert. Dabei fügen wir die Adresse und Position jedes Knotens in die Hashtabelle ein und die Adresse jedes Knotens in der neuen Liste in unser Array.

Wenn wir damit fertig sind, gehen wir die alte Liste und die neue Liste im Gleichschritt durch. Für jeden Knoten in der alten Liste sehen wir auf die Adresse im zufälligen Zeiger dieses Knotens. Wir schlagen die mit dieser Adresse verbundene Position in unserer Hashtabelle nach, erhalten dann die Adresse des Knotens in der neuen Liste an dieser Position und setzen sie in den zufälligen Zeiger des aktuellen Knotens in der neuen Liste. Dann gehen wir zum nächsten Knoten in der alten und neuen Liste über.

Wenn wir fertig sind, werfen/wir zerstören sowohl die Hashtabelle als auch das Array, da unsere neue Liste nun die Struktur der alten dupliziert und wir die zusätzlichen Daten nicht mehr benötigen.

Answer 2

Übersicht des Ansatzes
Wir werden nicht versuchen, von Anfang an eine neue verkettete Liste zu erstellen. Duplizieren Sie zuerst die Elemente in der Original verketteten Liste und teilen Sie dann die Liste in 2 identische Listen auf.

Die Details
Schritt 1 : Durchlaufen Sie die verkettete Liste mit den nächsten Zeigern und erstellen Sie eine Kopie jedes Knotens.

original :: A -> B -> C -> D -> E ->null

updated :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null

Dies kann leicht in einer einzigen Schleife erledigt werden.

Schritt 2 : Durchlaufen Sie die Liste erneut und beheben Sie die zufälligen Zeiger wie folgt

Node *current= start;
Node *newListNode, *random;
while (current!= null) {
    // Wenn der aktuelle Knoten einen zufälligen Zeiger hat, sagen wir current = A, A.random = D;
    if ( (*current)->random != null ) {
        // newListNode wird auf A' zeigen
        newListNode = (*current)->next;
        random = (*current)->random;
        random = (*random)->next;
        // Lassen Sie A' auf D's nächsten zeigen, der D' ist
        (*newListNode)->random = random;
    }
    // Hier A'.random = D'
    // Aktuelle geht zum nächsten Knoten in der Original liste => B , und nicht A'
    current= (*newListNode)->next;
}

Schritt 3 :: Teilen Sie die Liste in 2 Listen auf. Sie müssen nur die nächsten Zeiger hier korrigieren.

Original :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null
Neu :: A -> B -> C -> D -> E ->null
       A' -> B' -> C' -> D' -> E' ->null

Node *start1 = head;
Node *start2 = (*head) ->next      // Bitte überprüfen Sie die Grenzbedingungen selbst,
                                   // Ich gehe davon aus, dass die Eingabe eine gültige Liste war
Node *next, *traverse = start2;
while (traverse != null) {
    next = (*traverse)->next;
    if (next == null) {
        (*traverse)->next = null;
        break;
    }
    (*traverse)->next = (*next)->next;
    traverse = next;
}

Auf diese Weise haben Sie eine Kopie der Original liste in O(n) Zeit erstellt. Sie durchlaufen die Liste 3 Mal, was immer noch der Ordnung von n entspricht.

Answer 3

Klärungseditierung:

Das folgende funktioniert nur, wenn die "zufälligen" Zeiger eindeutig sind, wie von BowieOwens angemerkt.
Ich lasse die Antwort nur für die allgemeine Idee stehen, aber bitte nicht hochwerten, da sie definitiv falsch ist.

---

Wenn ich mich nicht vollkommen irre, kannst du dies ohne Verwendung von zusätzlichem Speicher tun.

Wenn du die alte Liste kopierst, speichere den random-Zeiger des alten Knotens im random-Zeiger des neuen Knotens.
Setze dann den random-Zeiger des alten Knotens auf den neuen Knoten.

Dies wird dir eine "Zig-Zag"-Struktur zwischen der alten Liste und der neuen Liste geben.

Pseudocode:

Node* alter_knoten = ;
Node * neuer_knoten = new Node;
neuer_knoten->random = alter_knoten->random;
alter_knoten->random = neuer_knoten;

Sobald du die alte Liste auf diese Weise kopiert hast, fängst du von vorne an, ersetzt aber die random-Zeiger so, dass die Zeiger in der alten Liste wiederhergestellt werden, während die random-Zeiger in der neuen Liste auf die entsprechenden neuen Knoten gesetzt werden:

Node* alter_zufall = alter_knoten->random->random; // alte Liste -> neue Liste -> alte Liste
Node* neuer_zufall = neuer_knoten->random->random; // neue Liste -> alte Liste -> neue Liste
alter_knoten->random = alter_zufall;
neuer_knoten->random = neuer_zufall;

Es sieht auf dem Papier viel besser aus, aber ich fürchte, meine ASCII-Kunstfähigkeiten reichen nicht aus.

Dies verändert die ursprüngliche Liste, aber sie wird in den ursprünglichen Zustand zurückversetzt.
Ob das zulässig ist, hängt wohl vom Interview ab, denke ich.

Answer 4

Wie Sie wissen sollten, bedeutet O(n) linear. Wenn Sie eine Kopie einer linearen Datenstruktur benötigen, werden Sie damit keine Probleme haben, da Sie einfach über die Knoten der ursprünglichen Liste iterieren müssen und für jeden besuchten Knoten einen neuen Knoten für die neue Liste erstellen werden. Ich denke, die Frage ist nicht gut formuliert, weil Sie einige Aspekte kennen müssen, um den Job zu erledigen wie: handelt es sich um eine zirkuläre Implementierung? Was ist der "nächste" Knoten? Der nächste Knoten eines Knotens oder der erste Knoten der Liste? Wie endet die Liste?

Answer 5

Vielleicht ist diese Frage ein Trick, um zu testen, wie du auf eigenartige Fragen antwortest, weil es eigentlich sehr einfach ist:

1) Iteriere durch jeden Knoten

2) Erstelle einen neuen Knoten für eine andere verkettete Liste und kopiere den Wert.

Die Kosten sind immer O(n): weil du nur einmal die gesamte verkettete Liste durchläufst!!!

Oder du hast etwas falsch verstanden bei seiner Frage.