Interviewfrage: Zwei sortierte sortierte einzeln verknüpfte Listen verschmelzen, ohne neue Knoten zu erstellen
https://stackoverflow.com//questions/10707352
-
13-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Dies ist eine Programmierfrage, die während eines schriftlichen Tests für ein Interview gestellt wurde. "Sie haben zwei einzeln verknüpfte Listen, die bereits sortiert sind, Sie müssen sie zusammenführen und einen Kopf der neuen Liste zurückgeben, ohne neue zusätzliche Knoten zu erstellen. Die zurückgegebene Liste sollte auch sortiert werden"
Die Methodensignatur ist: Knoten Mergelisten (Knotenliste1, Knotenliste2);
knotenklasse ist unten:
generasacodicetagpre.Ich habe viele Lösungen ausprobiert, aber keine extra-Knoten-Schrauben miteinander erstellt.Bitte helfen.
hier ist der begleitende Blogeintrag http://techieme.in/merging-two-sorted-Singly-Linked-Liste /
Lösung
Andere Tipps
Rekursion sollte nicht benötigt werden, um nicht zu vermeiden, dass ein neuer Knoten zugewiesen wird:
generasacodicetagpre.Hier ist der Algorithmus, wie Sie zwei sortierte verknüpfte Listen A und B zusammenführen:
generasacodicetagpre.Hier ist c die Ausgabeliste.
Aussehen ma, keine Rekursion!
generasacodicetagpre.Iteration kann wie folgt erfolgen.Komplexität= o (n)
generasacodicetagpre.Dies kann nicht erfolgen, ohne den zusätzlichen Knoten zu erstellen, wobei nur eine andere Knotenreferenz, die an die Parameter (Knoten Temp) verläuft.
generasacodicetagpre.Ich möchte teilen, wie ich die Lösung dachte ... Ich sah die Lösung, die Rekursion beinhaltet, und sie sind ziemlich erstaunlich, ist das Ergebnis des gut funktionalen und modularen Denkens.Ich schätze das Teilen wirklich.
Ich möchte hinzufügen, dass der Rekursion nicht für große Lits funktioniert, die Stapelanrufe werden überlaufen;Also entschied ich mich, den iterativen Ansatz zu probieren ... und das bekomme ich.
Der Code ist ziemlich selbsterklärend, ich habe einige Inline-Kommentare hinzugefügt, um dies zu versichern.
Wenn Sie es nicht verstehen, benachrichtigen Sie mich bitte und ich werde die Lesbarkeit verbessern (vielleicht habe ich eine irreführende Interpretation meines eigenen Codes).
generasacodicetagpre.}
Eine einfache iterative Lösung.
generasacodicetagpre.Ich zeige unter einer iterativen Lösung.Eine rekursive Lösung wäre kompakter, aber da wir nicht die Länge der Listen kennen, betreibt die Rekursion die Gefahr des Stapelüberlaufs.
Die Grundidee ähnelt dem Zusammenführungsschritt in der Zusammenführungssorte;Wir halten einen Zeiger, der jeder Eingangsliste entspricht;Bei jeder Iteration bewegen wir den Zeiger, der dem kleineren Element entspricht.Es gibt jedoch einen entscheidenden Unterschied, in dem die meisten Menschen ausgelöst werden.In der Zusammenführungs-Sortierung, da wir ein Ergebnisarray verwenden, ist die nächste Position der nächsten Position immer der Index des Ergebnisarrays.Für eine verknüpfte Liste müssen wir einen Zeiger auf das letzte Element der sortierten Liste behalten.Der Zeiger kann von einer Eingabeliste auf einen anderen springen, je nachdem, welches das kleinere Element für die aktuelle Iteration hat.
Damit sollte der folgende Code selbsterklärend sein.
generasacodicetagpre.Zunächst einmal den Mittelwert von "verstehen, ohne neue zusätzliche Knoten zu erstellen" , wie ich es verstehe, nicht bedeutet, dass ich keine Zeiger (en) kann, die auf einen vorhandenen Knoten verweist (s).
Sie können es nicht erreichen, ohne auf vorhandene Knoten zu sprechen, selbst wenn Sie die Rekursion verwenden, um das gleiche zu erreichen, erstellt das System Zeiger für Sie als Anrufstapel.Es ist wie das Erzählen des Systems, um Zeiger hinzuzufügen, die Sie in Ihrem Code vermieden haben.
einfache Funktion, um das gleiche
Siehe mein Blogbeitrag für http://www.algorithmsandme.com/2013/10/link-list-merge-two-sorted-linked.html
Hier ist ein komplettes Arbeitsbeispiel, das die verknüpfte Liste verwendet, die Java.Util implementiert ist.Sie können einfach kopieren, indem Sie den Code unten in einer Haupt- () -Methode einfügen.
generasacodicetagpre.
Überlegen Sie unten die verknüpfte Liste, um dies zu visualisieren
2>4 liste a
1>3 list b
Betrachten Sie das Beispiel
5->10->15>21 // List1
2->3->6->20 //List2
Meine Übernahme Die Frage ist wie folgt:
pseudocode:
generasacodicetagpre.Code:
generasacodicetagpre.) glbmp
Ich habe zu Beginn nur einen Dummy-Knoten erstellt, um mich viele 'IF' -Es zu retten.
generasacodicetagpre.Hier ist der Code, wie Sie zwei sortierte verknüpfte Listen-Köpfe und Heads zusammenführen:
generasacodicetagpre.