VerketteteListe divide und Zusammenführen in umgekehrter Reihenfolge

Question

Ich habe eine verkettete Liste als 1->2->3->4->5->6

ich es 1->6->2->5->3->4

zum ersten Element verbunden ielast Element ändern müssen, letzte zweite Element mit dem zweiten Element verbunden und so auf.

Ich benutzte 2 Zeiger, einen schnellen und einen langsamen. Sobald ich die Mitte erreiche, lege ich alle Elemente in der zweiten Hälfte in einen Stapel. [4, 5, 6]

nun einen dritten Zeiger verwenden, ich die ursprüngliche verknüpfte Liste durchlaufen und legen Sie Knoten aus dem Stapel dh pop [6, 5, 4]

Gibt es eine bessere Lösung als diese ?

Answer 1

Ich denke, das ist optimal.
Ich verwende 2 Zeiger. Ein langsamer, ein Sprung zu einem Zeitpunkt und andere schnelle, 2 Sprünge gleichzeitig.
Daher finde ich die Mitte und auch die Mitte zählen.
Jetzt, von der Mitte bis zum Ende, kehre ich die verkettete Liste um.
Ich habe jetzt zwei verknüpfte Listen, eine von Anfang bis Mitte und andere umgekehrt von Mitte zu Ende.
Nehmen Sie einfach ein Element aus Liste 1 und verknüpfen Sie das Element von Link 2 mit diesem und inkrementieren Sie beide Listen. Kein zusätzlicher Platzbedarf und Zeitaufwand ist erforderlich. O (N)