Umkehren einer verketteten Liste

Question

Beim Umkehren der Liste verwende ich den folgenden Code, aber es fügt das letzte Element zweimal hinzu.

public void reverse() 
    { 
     Node current,previous,next; 
     current=head; 
     previous=null; 
     while(current!=null) 
     { 
      next=current.getNext(); 
      current.setNext(previous); 
      previous=current; 
      current=next; 
     } 
     head=previous; 
    } 

Die Knotenklasse folgt

public class Node 
{ 
    private Node next; 
    private String data; 

    public Node(String dataValue) { 
     next = null; 
     data = dataValue; 
    } 

    public Node getNext() { 
     return next; 
    } 

    public void setNext(Node next) { 
     this.next = next; 
    } 

    public String getData() { 
     return data; 
    } 

    public void setData(String data) { 
     this.data = data; 
    } 
} 

ich die Daten von

folgende

public void add(String data) 
    { 
     if(head==null) 
     { 
      head=new Node(data); 
     } 
     Node temp=new Node(data); 
     Node current=head; 
     if(current!=null) 
     { 
      while(current.getNext()!=null) 
      { 
       current=current.getNext(); 
      } 
      current.setNext(temp); 
     } 
    } 

Nach der Umkehrung der Liste in der Liste am Addieren der Ausgabe I folgt

bin immer

Ursprüngliche Liste: [1] [2] [3] [4] [5] Umgekehrte Liste: [4] [3] [2] [1] [1 ]

Answer 1

Ihr Problem ist in der add Methode, wenn es no head so weit ist, können Sie sich als next node, wie neben vermeiden eine return Anweisung hinzufügen müssen hinzufügen:

public void add(String data) 
{ 
    if(head==null) 
    { 
     head=new Node(data); 
     // Exit of the method to prevent adding the head as next element 
     // of the head 
     return; 
    } 
    ... 
} 

Mit dieser einfachen Änderung, wenn ich tun :

// Create the list 
MyList list = new MyList(); 
list.add("1"); 
list.add("2"); 
list.add("3"); 
list.add("4"); 
list.add("5"); 

// Print the list content 
current = list.head; 
while(current != null){ 
    System.out.println(current.getData()); 
    current = current.getNext(); 
} 

// Inverse the list 
list.reverse(); 
System.out.println("****"); 
// Print again the list content 
current = list.head; 
while(current != null){ 
    System.out.println(current.getData()); 
    current = current.getNext(); 
} 

Ausgang:

1 
2 
3 
4 
5 
**** 
5 
4 
3 
2 
1 

Answer 2

Beim Füllen Ihrer Liste wird der Kopf auf [1] gesetzt und hinter diesem Kopf wird ein Knoten [1] eingefügt. Sie haben also immer das erste Element Ihrer Liste zweimal.

Sie würden besser java.list.LinkedList verwenden, die Sie mit Node

List<Node> yourList = new LinkedList<Node>(); 
yourList.add(new Node(1)); 
yourList.add(new Node(2)); 

füllen Sie können dann Ihre Liste rückgängig machen, indem einfach ausgeführt wird:

Collections.reverse(yourList);