Umkehren einer verketteten Liste rekursiv in Java

Question

Ich versuche, eine umgekehrte Linkliste zu erreichen. Die neue Liste muss rekursiv erstellt werden.

Ich erstelle den ersten Knoten in der umgekehrten Liste und ich versuche, eine Unterliste Next zu erstellen, die das nächste Element als next.next hat und schließlich diese Unterliste als neben dem Knoten zuweisen. Das Problem ist, dass der nächste Knoten NIL bleibt, obwohl ich ihn in der for-Schleife neu erstellt habe.

Bearbeiten: Die Funktion darf nicht ändern (Argumente hinzufügen), weil einige Tests darauf ausgeführt werden.

class Node { 
    private Object item; 
    private Node next,current; 

    public Node(Object o, Node n) { 
     this.item = o; 
     this.next = n; 
    } 

    public Node(Node n) { 
    } 

    public static final Node NIL = new Node(Node.NIL, Node.NIL); 

    public Object getItem() { 
     return this.item; 
    } 

    public Node getNext() { 
     return this.next; 
    } 

    public void setItem(Object o) { 
     this.item = o; 
    } 

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

    // this method returns the item with index number i 
    public Object nthItem(int i) { 
     Node p = this; 
     while (p!=null){ 
      for (int k=1;k<=i;k++){ 
       p=p.next; 
      } 
      return p.item; 
     } 
     return null; 
    } 

    // this method returns the the next item of the node 
    public Node nthNext(int i) { 
     Node p = this; 
     while (p!=null){ 
      for (int k=1;k<=i;k++){ 
       p=p.next; 
      } 
      return p.getNext(); 
     } 
     return null; 
    } 

    public Node nthNode(int i) { 
     Node p = this; 
     while (p!=null){ 
      for (int k=1;k<=i;k++){ 
       p=p.next; 
      } 
      return p; 
     } 
     return NIL; 
    } 

    public int length(){ 
     if (this == NIL) return 0; 
     else return 1 + next.length(); 
    } 

    public Node remove(Object o){ 
     Node p = this; 
     if (p == NIL) return NIL; 
     else if(p.item == o) { 
      p = p.next; 
      return p.remove(o); 
     } 
     else return new Node(p.item, p.next.remove(o)); 
    } 

    public Node reverse() { 
     int i = this.length()-1; 
     if(this == NIL) return NIL; 

     Node node = new Node(Node.NIL, Node.NIL); 

     Node next = NIL; 

     //create the first node in the reversed list 
     if(i >= 1) node = new Node(nthItem(i), next); 
     else node = new Node(nthItem(i), Node.NIL); 

     //iterate through the original list and create a next node 
     if (i>0) { 
      for (int k=i; k>=0; k--){ 
       if (k<=0) { 
        next = NIL; 
       } 
       else { 
        next = new Node(nthItem(k-1),next); 
       }    
      } 
     } 

     //debugging in console 
     System.out.println("final node = " + next.item+" "); 
     return node; 
    } 
} 

class Test{ 

    public static void main(String[] string){ 
     Node n = new Node(1, Node.NIL); 
     Node nn = new Node(2, n); 

     Node r = nn.reverse(); 

     System.out.println("\t item " + r.getItem()+ " " + r.getNext().getItem() + " length " + r.length()); 
    } 
} 

Answer 1

Dies ist eine Frage, ob die impliziten Stapel versteht entworfen zu testen. Jedes Mal, wenn Sie einen rekursiven Aufruf durchführen, fügen Sie einen Stapelrahmen hinzu. Betrachten Sie den Stapel so, als ob Sie die Routine iterativ ausführen würden.

Um die Liste zu umkehren:

1. Stapel alle Elemente, um
2. durch knallen jedes Element eine neue Liste machen.

Jetzt wandeln diese in eine rekursive Aufruf

//in [1,2,3,null] 
Node reverse(Node n){ 

    //base case 
    if(n == null) 
    { 
     return null; 
    } 

    // returns [null,3,2,1] 
    Node next = reverse(n.getNext()); 
    next.setNext(n);// set the next nodes next to its previous(n on unwinding) 
    return n; 
} 

Beachten Sie, dass die umgekehrte Verfahren hier nicht den neuen Kopf zurückkehrt, um den Kopf der umgekehrten Liste gehen Sie wie folgt zu erhalten, vielleicht machen die über einem Helfer stattdessen.

Node oldHead = n; 
Node newHead = tail(n); 
oldHead.reverse();