Wie rekursive einfach verknüpfte Liste (C++)

Question

machen Mein Buch fordert mich auf, eine rekursive Definition einer einfach verknüpften Liste zu machen. Ich habe überhaupt keine Ahnung, wie ich das machen soll. Kann mir bitte jemand mit einer Probe helfen? Danke

Answer 1

Es ist wie eine normale verkettete Liste, außer dass die Iteration durch Rekursion und nicht durch Schleifen durchgeführt wird.

Zuerst ein wenig Leselicht:

Zum Beispiel kann eine Loop-basierte Funktion den letzten Knoten zu finden sein könnte:

Node * getLast(Node * current) 
{ 
    while (current->next == null) 
    { // loop until no more nodes 
     current = current.next; 
    } 
    return current; // return last node 
} 

Während die rekursive Version nur überprüft, ob der aktuelle Knoten die letzte und ruft sich mit dem nächsten Knoten auf, wenn es einen nächsten Knoten gibt.

Node * getLast(Node * current) 
{ 
    if (current->next == null) 
    { // found last node. return it 
     return current; 
    } 
    else 
    { // see if next node is last node 
     return getLast(current->next); 
    } 
}