Ich frage mich, ob es eine Logik gibt, eine einfach verknüpfte Liste mit nur zwei Zeigern umzukehren.
Im Folgenden wird die einzelne verknüpfte Liste mit drei Zeigern nämlich umkehren p
, q
, r
:
struct node {
int data;
struct node *link;
};
void reverse() {
struct node *p = first,
*q = NULL,
*r;
while (p != NULL) {
r = q;
q = p;
p = p->link;
q->link = r;
}
first = q;
}
Gibt es eine andere Alternative, um die verknüpfte Liste umzukehren? Was wäre die beste Logik, um eine einfach verknüpfte Liste in Bezug auf die Zeitkomplexität umzukehren?
Antworten:
Irgendeine Alternative? Nein, das ist so einfach wie es nur geht und es gibt keinen grundlegend anderen Weg, dies zu tun. Dieser Algorithmus ist bereits O (n) -Zeit und Sie können nicht schneller werden, da Sie jeden Knoten ändern müssen.
Es sieht so aus, als ob Ihr Code auf dem richtigen Weg ist, aber in der obigen Form funktioniert er nicht ganz. Hier ist eine Arbeitsversion:
quelle
reverse()
Funktion zuerst eingestellt werden sollte, glaube ich. Andernfalls funktionierte der ursprüngliche Code einwandfrei, wenn er an Ihr ordentliches Testkabel angeschlossen wurde. Sie erhalten trotzdem +1 von mir - aber eine Erklärung dessen, was Sie als "offensichtliche Fehler" betrachten, würde Ihre Antwort verbessern.Ich hasse es, schlechte Nachrichten zu überbringen, aber ich glaube nicht, dass Ihre Drei-Zeiger-Lösung tatsächlich funktioniert. Als ich es im folgenden Testkabel verwendete, wurde die Liste gemäß der folgenden Ausgabe auf einen Knoten reduziert:
Sie erhalten keine bessere Zeitkomplexität als Ihre Lösung, da es O (n) ist und Sie jeden Knoten besuchen müssen, um die Zeiger zu ändern. Sie können jedoch ganz einfach eine Lösung mit nur zwei zusätzlichen Zeigern erstellen, wie im folgenden Code gezeigt:
Dieser Code gibt aus:
was ich denke, ist das, wonach du gesucht hast. Dies ist tatsächlich möglich, da Sie nach dem Laden
first
in den Zeiger, der die Liste durchläuft,first
nach Belieben wiederverwenden können .quelle
first
Zeigers in der verknüpften Liste selbst kann die Lösung nur 2 zusätzliche Zeiger verwenden, dafür sind jedoch noch 3 Gesamtzeiger erforderlich.first
. Auf die gleiche Weise die Drei-Zeiger - Lösung OP hattefirst
,p
,q
undr
.quelle
Hier ist der Code , um eine einzeln verknüpfte Liste in C umgekehrt .
Und hier wird es unten eingefügt:
quelle
Ja. Ich bin sicher, Sie können dies genauso tun, wie Sie zwei Zahlen tauschen können, ohne eine dritte zu verwenden . Setzen Sie die Zeiger einfach auf int / long und führen Sie die XOR-Operation einige Male aus. Dies ist einer dieser C-Tricks, die für eine lustige Frage sorgen, aber keinen praktischen Wert haben.
Können Sie die O (n) -Komplexität reduzieren? Nein nicht wirklich. Verwenden Sie einfach eine doppelt verknüpfte Liste, wenn Sie glauben, dass Sie die umgekehrte Reihenfolge benötigen.
quelle
Robert Sedgewick, " Algorithmen in C ", Addison-Wesley, 3. Auflage, 1997, [Abschnitt 3.4]
Falls dies keine zyklische Liste ist, ist NULL der letzte Link.
quelle
Nur zum Spaß (obwohl die Optimierung der Schwanzrekursion verhindern sollte, dass der gesamte Stapel verschlungen wird):
quelle
Um zwei Variablen ohne Verwendung einer temporären Variablen auszutauschen,
Der schnellste Weg ist, es in eine Zeile zu schreiben
Ähnlich,
mit zwei Swaps
Lösung mit xor
Lösung in einer Zeile
Dieselbe Logik wird verwendet, um eine verknüpfte Liste umzukehren.
quelle
intptr_t
) nicht funktioniert . Interessant - auf diese Weise zu tauschen ist auf modernen Systemen nicht optimal.Sie benötigen einen Spurzeiger, der die Liste verfolgt.
Sie benötigen zwei Zeiger:
erster Zeiger zum Auswählen des ersten Knotens. zweiter Zeiger zur Auswahl des zweiten Knotens.
Wird bearbeitet :
Spurzeiger verschieben
Zeigen Sie mit dem zweiten Knoten auf den ersten Knoten
Bewegen Sie den ersten Zeiger um einen Schritt, indem Sie einem den zweiten Zeiger zuweisen
Bewegen Sie den zweiten Zeiger um einen Schritt, indem Sie dem zweiten den Spurzeiger zuweisen
}}
quelle
Wie wäre es mit dem besser lesbaren:
quelle
Hier ist eine einfachere Version in Java. Es werden nur zwei Zeiger
curr
& verwendetprev
quelle
Berechnen Sie die zeitliche Komplexität des Algorithmus, den Sie jetzt verwenden, und es sollte offensichtlich sein, dass er nicht verbessert werden kann.
quelle
Ich verstehe nicht, warum es notwendig ist, den Kopf zurückzugeben, da wir ihn als Argument übergeben. Wir übergeben den Kopf der Linkliste, dann können wir auch aktualisieren. Unten ist eine einfache Lösung.
quelle
quelle
Nein, nichts schnelleres als das aktuelle O (n) kann getan werden. Sie müssen jeden Knoten ändern, damit die Zeit ohnehin proportional zur Anzahl der Elemente ist und das ist O (n), das Sie bereits haben.
quelle
Die Verwendung von zwei Zeigern unter Beibehaltung der Zeitkomplexität von O (n), die am schnellsten erreichbar ist, ist möglicherweise nur durch Zahlenumwandlung von Zeigern und Vertauschen ihrer Werte möglich. Hier ist eine Implementierung:
quelle
Ich habe einen etwas anderen Ansatz. Ich wollte die vorhandenen Funktionen (wie insert_at (Index), delete_from (Index)) nutzen, um die Liste umzukehren (so etwas wie eine Rechtsverschiebungsoperation). Die Komplexität ist immer noch O (n), aber der Vorteil ist mehr wiederverwendeter Code. Schauen Sie sich eine andere_reverse () -Methode an und lassen Sie mich wissen, was Sie alle denken.
quelle
quelle
quelle
Ja, es gibt eine Möglichkeit, nur zwei Zeiger zu verwenden. Dies geschieht durch Erstellen einer neuen verknüpften Liste, wobei der erste Knoten der erste Knoten der angegebenen Liste ist und der zweite Knoten der ersten Liste am Anfang der neuen Liste hinzugefügt wird und so weiter.
quelle
Hier ist meine Version:
wo
quelle
Ich verwende Java, um dies zu implementieren, und der Ansatz ist eine testgetriebene Entwicklung, daher sind auch Testfälle beigefügt.
Die Knotenklasse, die einen einzelnen Knoten darstellt -
Serviceklasse, die den Startknoten als Eingabe verwendet und ohne zusätzlichen Speicherplatz reserviert.
Und der Testfall, der das obige Szenario abdeckt. Bitte beachten Sie, dass Sie Junit-Gläser benötigen. Ich benutze testng.jar; Sie können alles verwenden, was Ihnen gefällt.
quelle
Ein einfacher Algorithmus, wenn Sie die verknüpfte Liste als Stapelstruktur verwenden:
Die Leistung kann beeinträchtigt werden, da zusätzliche Funktionen für add und malloc aufgerufen werden, sodass die Algorithmen für Adressentausch besser sind, diese jedoch tatsächlich eine neue Liste erstellt, sodass Sie zusätzliche Optionen wie das Sortieren oder Entfernen von Elementen verwenden können, wenn Sie der Funktion eine Rückruffunktion als Parameter hinzufügen umkehren.
quelle
Hier ist ein etwas anderer, aber einfacher Ansatz in C ++ 11:
Ausgabe hier
quelle
Es folgt eine Implementierung mit 2 Zeigern (head und r).
quelle
sizeof(size_t) < sizeof(ListNode*)
... Sie verwenden solltenstd::uintptr_t
.Hier ist eine kleine einfache Lösung ...
quelle
Sie können dieses Problem mit nur einem zusätzlichen Zeiger lösen, der für die Umkehrfunktion statisch sein muss. Es ist in O (n) Komplexität.
quelle
Alternativ können Sie die Rekursion verwenden.
quelle
quelle
quelle