Umkehren einer verketteten Liste in Java, ohne das Original zu ändern

Question

Ich versuche eine verkettete Liste umzukehren, die funktioniert, aber wenn ich versuche, das Original zu drucken, schlägt es fehl (druckt nur den Kopf). Meine Frage ist, warum würde die Umkehrung das Original beeinflussen. Unten ist mein Code. LinkedList ist meine eigene Klasse, also auch Node. Wenn ich vor dem Rückwärtsfahren versuche, meine Liste zu drucken, funktioniert das.

public static void main(String[] args) { 
    LinkedList list; 
    ... 
    Node head = list.getHead(); 
    Node rev = reverse(head); 
    Node temp = rev; 
    while (temp != null) { 
     System.out.println(temp); 
     temp = temp.next; 
    } 

    temp = head; 
    while (temp != null) { 
     System.out.println(temp); 
     temp = temp.next; 
    } 
} 

private static reverse(Node head) { 
    // Reversing the linked list 
} 

EDIT :: Dies scheint eine Java Sache zu sein. Java übergibt ein Objekt als Referenz. Wenn ich den Kopf als Parameter überlasse, wird er als Referenz übergeben, und jede Änderung, die daran vorgenommen wird, spiegelt sich in der aufrufenden Funktion wider. Doing Node h = Kopf und dann übergeben h als Parameter wird auch nicht funktionieren, da h das gleiche Objekt wie Kopf sein wird. Die einzige Option, die ich mir vorstellen kann, besteht darin, ein neues Objekt zu erstellen, die verknüpfte Liste zu kopieren und diese als Parameter zu übergeben.

Meine Frage wird, gibt es eine bessere Lösung?

Answer 1

es zu verstehen, Bild sieht Ihre Liste wie diese

list (list.head =a) --> a (a.next=b) --> b (b.next= c) -> c (c.next = null) 

Wenn Sie den Kopf bekommen, dann sind Sie immer Objekt ‚a‘. Dann ändern Sie das Objekt 'a'. So können Sie sehen, dass Sie die Liste bearbeiten, indem Sie dies tun.

Was Sie tun müssen, ist: den Kopf Get eine Kopie erstellen die Kopie umkehren das nächste Element Get es Kopieren sie es an die letzte Join umkehren Und so weiter

Da Sie Verwenden Sie Ihre eigenen Klassen nicht Java-Klassen Sammlungen, ist der einfachste Weg für Sie sicherzustellen, dass reverseNode() nur eine Kopie der, die Sie übergeben, und die Kopie zurückgibt. Zuerst stellen Sie sicher, hat Ihre Node-Klasse einen Konstruktor, der Kopien ein anderer Knoten, dann so etwas tun:

private static Node reverse(Node original) 
{ 
    Node retval = new Node(original); 
    // or you could use clone() as Bhavik suggested, if your Node class implements it 
    // modify retval 
    // I haven't shown code to reverse it as I assume you already have that and you didnt specify if it was a bidirectional list or just one direction. 

    return retval; 
} 

Oder Sie könnten eine statische Methode in der Klasse Knoten hinzufügen, die einen neuen Knoten konstruiert, die umgekehrt ist:

static Node createReverse(Node n) 
{ 
    return new Node(n.data,n.next,n.prior); 
} 

Oder eine nicht statische Methode der Knotenklasse, die eine umgekehrte Kopie von sich selbst zurückgibt;

Node createReverse() 
{ 
    return new Node(this.data,this.next,this.prior); 
} 

Aber Sie sollten dies berücksichtigen kann sehr hässlich, da die Kopien noch Zeiger haben wird in die bestehende Liste zeigen!

Eine bessere Technik könnte darin bestehen, eine neue leere Liste zu erstellen und dann am Ende des Originals zu beginnen, eine Kopie zu erstellen und sie zum Anfang Ihrer neuen Liste hinzuzufügen.

Sie können die Rekursion dazu verwenden, aber es könnte leicht zu wenig Speicher zur Verfügung stehen.

Aber anstatt dies manuell zu tun, könnten Sie sich die Pakete java.util ansehen und zur Verwendung eines ihrer LinkedList- und Listenelementtypen wechseln. Diese Klassen haben bereits alle Probleme mit diesem Zeug gelöst.

Dann könnten Sie (wenn Sie die ursprüngliche Liste unverändert beibehalten müssen): - Erstellen Sie eine Kopie Ihrer gesamten Liste. - Kopieren Sie die Kopie wie folgt:

Wenn Sie sich nicht darum kümmern, das Original zu behalten, dann verwenden Sie einfach diese Methode (unten) auf Ihrer Liste, keine Notwendigkeit, dann eine Kopie zu machen.

Von java.util.Collections:

Collections.reverse(List a_list); 

Die Sammlungen Klasse wird eine effiziente Möglichkeit, wählen Sie die Liste rückgängig zu machen, je nachdem, ob es sich um eine bidirektionale, unidirektionalen usw.

Answer 2

Chunko Antwort ist Genau darin sollten Sie Kopien Ihrer Knoten erstellen, anstatt nur Referenzen an sie zu übergeben.
Aber ich denke, man könnte dies sein Grübeln:

LinkedList

LinkedList reversedList = new LinkedList(); 
for (int i = originalList.size()-1; i >= 0; i--) { 
    reversedList.add(list.get(i)); 
} 

Java hat keine getHead() Methode, so dass ich denke, Sie verwenden einige Hausaufgaben im Zusammenhang mit benutzerdefinierten Implementierung einer verketteten Liste. Dennoch sollte Ihre Implementierung eine add() Methode haben, die eine neue Node an die Liste anfügt, sowie eine get(int) Methode, die das Element an einer bestimmten Position zurückgibt.
Sie können diese Methoden verwenden, um eine neue Liste zu erstellen und sie mit den ursprünglichen Elementen der Liste in umgekehrter Reihenfolge aufzufüllen.