umgekehrte doppelt verkettete Liste mit Rekursion

Question

Ich schreibe Programm, um doppelt verkettete Liste mit Rekursion umzukehren. Ich kann iterativ implementieren. aber in Rekursion stecken. Hier

ist, was ich habe

public static Node reverseRecurseDoubleLinkedList(Node node){ 
     if (node==null || node.next==null) 
      return node; 
     Node newNode = reverseRecurseDoubleLinkedList(node.next); 
     node.next.next=node; 
     node.next=null; 
     node.prev=newNode; 
     return newNode; 
    } 

Ich sehe die prev Zeiger sind nicht richtig eingestellt. aber next Zeiger sind in der Tat richtig.

Dank

Answer 1

In der Regel eine Möglichkeit, über rekursive Code zu vereinfachen Denken ist nur die Garantien zu berücksichtigen, die angeboten werden, wenn ein rekursive Aufruf abgeschlossen ist. Sie müssen dann überprüfen, ob diese Garantien im Basisfall gelten, der die Rekursion stoppt (z. B. leere Liste oder Liste mit einem einzelnen Knoten), und dass sie bei jedem zusätzlichen rekursiven Aufruf beibehalten werden.

Es gibt ein paar Probleme im Code zur Verfügung gestellt:

• die Bedingung, die Rekursion beendet nicht richtig die Situationen behandeln hat, als node.next == null. Das Feld node.prev sollte in diesem Fall auf null gesetzt sein.

• Der Variablenname newNode kann zu Verwirrung führen. Es stellt den neuen Kopf der umgekehrten Liste dar (die das Ende der ursprünglichen Liste war). Ich habe es in newHead umbenannt.

• In Bezug auf den obigen Punkt ist die Zuweisung node.prev=newNode; nicht korrekt - wir wollen nicht die prev jedes Knotens auf den Kopf der neuen Liste zeigen.

Nach diesen Aspekten enthält, kehrt der folgende Code korrekt die Liste:

public static Node reverseRecurseDoubleLinkedList(Node node) { 
    if (node == null) { 
     return node; 
    } 

    if (node.next == null) { 
     node.prev = null; 
     return node; 
    } 

    Node newHead = reverseRecurseDoubleLinkedList(node.next); 
    node.next.next = node; 
    node.prev = node.next; 
    node.next = null; 

    return newHead; 
}