Rekursive verknüpfte Liste. Was mache ich falsch?

Question

public class Reverse { 

    public static void printLL(Node head) { 
     while(head!=null){ 
      System.out.print(head.getData()+"-->"); 
      head=head.next; 
     } 
    } 

    public static Node reverseLL(Node head){ 
     if(head == null) { 
      return head; 
     } 
     return reverseLL(head.next); 
    } 

    public static void main(String[] args) { 
     Node first=new Node(10); 
     Node head=first; 
     Node second=new Node(20); 
     first.next=second; 
     Node third=new Node(30); 
     second.next=third; 
     Node fourth=new Node(40); 
     third.next=fourth; 
     printLL(head); 
     System.out.println("\nReverse of Linked List is \n"); 
     head=reverseLL(head); 
     printLL(head); 
    } 
} 

Hier ist mein Code. Es druckt nichts.

Ich denke, dass aufgrund der Rekursion auf den Nullzeiger zeigt und daher keine Daten an der Nullposition vorhanden sind.

Bitte sagen Sie mir, was ich tun kann, um den Code korrekt zu machen.

Vielen Dank im Voraus

Answer 1

Das Problem ist, dass Ihr reverseLL nichts, nachdem sie der head macht sich selbst rekursiv aufruft.

Das Basisgehäuse ist richtig: Wenn headnull ist, geben Sie null zurück. Der rekursive Schritt ist jedoch nicht vollständig: Sie müssen den Rest der Liste umkehren, aber dann müssen Sie ihn an die head anhängen.

Der einfachste Weg, dies zu tun ist ein zusätzlichen Parameter für die prior Knoten passieren, so dass Sie

head.next = prior; 

in Ihrer rekursive Methode tun könnten. Hier ist, wie Sie Ihre „Wrapper“ Methode aussehen würde:

public static Node reverseLL(Node head) { 
    if(head==null){ 
     return null; 
    } 
    return reverseLL(head, null); 
} 

Beachten Sie, dass es nicht rekursiv ist - das alles tut ruft eine zweiargumentigen Überlastung.

Das rekursive Verfahren weiß, dass head ist nie null, so dass ihr Basisfall ist head.next == null:

public static Node reverseLL(Node head, Node prior) { 
    Node res; 
    if (head.next == null) { 
     res = head; 
    } else { 
     res = reverseLL(head.next, head); 
    } 
    head.next = prior; 
    return res; 
} 

Die Umkehr des head Knoten bei der Zuweisung erfolgt vor dem return. Beachten Sie, wie die Methode den letzten Nicht-Null-Knoten in der Kette zurückgibt.

Demo

Answer 2

Ihre reverseLL einfach geht durch alle Knoten, und wenn es das letzte erreicht if(head==null) tun, wird null zurückgegeben.

Sie müssen die reverseLL Funktion beheben. Fügen Sie der Funktion Traces hinzu, um Schritt für Schritt zu verstehen, was sie tut.

Answer 3

Sie scheinen einen entscheidenden Punkt über Rekursion verpasst zu haben - Sie müssen sich selbst nennen.

Ich werde eine Änderung an printLL vorschlagen, die eine mögliche rekursive Lösung zeigen sollte, die funktionieren sollte.

public static void printLL(Node head) { 

    if (head != null) { 
     System.out.print(head.getData() + "-->"); 
     printLL(head.next); 
    } 
} 

Hinweis, wie der Code im Grunde sagt, wenn es ein Kopf ist, drucken Sie es Daten ist und dann drucken Sie es head.next ist.