Inverser une liste de liens de façon récursive en c

solution alternative:

struct node *head;
void reverse(struct node *prev, struct node *cur)
{
   if(cur){
      reverse(cur,cur->link);
      cur->link = prev;
    }
    else{
      head = prev;
    }
}

Dans main, appel inverse(NULL,tête);

/* Reverses a linked list, returns head of reversed list
*/
NodePtr reverseList(NodePtr curr) {
    if (curr == NULL || curr->next == NULL) return curr; // empty or single element case

    NodePtr nextElement = curr->next;
    curr->next = NULL;
    NodePtr head = reverseList(nextElement);
    nextElement->next = curr;
    return head;
}

une autre solution:

struct node *reverse_recur(struct node *temp)
{
    if(temp->link==NULL)
    {
        return temp;
    }

    struct node *temp1=temp->link;

    temp->link=NULL;

    return (reverse_recur(temp1)->link=temp);

}

que la liste des liens soit 1-> 2 -> 3 ->4

la fonction en c est--

struct linked_node * reverse_recursive(struct linked_node * head)
{
struct linked_node * first;/*stores the address of first node of the linked
list passed to function*/
struct linked_node * second;/* stores the address of second node of the
linked list passed to function*/
struct linked_node * rev_head;/*stores the address of last node of initial 
linked list. It also becomes the head of the reversed linked list.*/
//initalizing first and second
first=head;
second=head->next;
//if the linked list is empty then returns null
if(first=NULL)
   return(NULL);
/* if the linked list passed to function contains just 1 element, then pass
address of that element*/
if(second==NULL)
   return(first);
/*In the linked list passed to function, make the next of first element 
 NULL. It will eventually (after all the recursive calls ) make the
 next of first element of the initial linked list NULL.*/
first->next=NULL;
/* storing the address of the reverse head which will be passed to it by the
 condition if(second==NULL) hence it will store the address of last element
 when this statement is executed for the last time. Also here we assume that 
the reverse function will yield the reverse of the rest of the linked 
list.*/
rev_head=reverse(second);
/*making the rest of the linked list point to the first element. i.e. 
 reversing the list.*/
second->next=first;

/*returning the reverse head (address of last element of initial linked 
list) . This condition executes only if the initial list is 1- not empty 
2- contains more than one element. So it just relays the value of last 
element to higher recursive calls.  */
return(rev_head);
}

exécute maintenant la fonction pour la liste liée 1-> 2-> 3 -> 4

• à l'intérieur marche arrière(&1) le code s'exécute jusqu'à ce que rev_head=reverse(&2); // ici &1 est l'adresse 1.

liste de fonction

1(première)->2(deuxième) -> 3 -> 4

• à l'intérieur marche arrière(&2) le code s'exécute jusqu'à ce que rev_head=reverse(&3); liste des la fonction
  
  2(première)->3 (deuxième)-> 4

• à l'intérieur marche arrière(&3) le code s'exécute jusqu'à ce que rev_head=reverse (&4); liste si la fonction
  
  3(première)-> 4 (seconde)

• à l'intérieur marche arrière(&4) fin de la condition second = = nul est vrai donc le retour est exécuté et adresse de 4 est renvoyée.

liste des fonctions

4(première)-> NULL(seconde)

• retour à l'arrière(&3) liste des la fonction est
  
  NULL<-3(premier) 4 (seconde)
  
  et la valeur de rev_head=&4, qui a été retournée

après l'exécution de seconde->suivant=premier; liste devient

NULL<- 3(premier) <-4 (seconde)

retour (rev_head ); est exécuté qui passe &4 parce que rev_head=&4

• retour à la rev(&2)

liste en fonction est

NULL<-2(premier) 3(seconde)<-4

et rev_head est &4 qui a été retourné par rev (&3)

après l'exécution de seconde->suivant=tout d'abord , la liste devient

NULL<-2(premier)<-3(seconde)<-4

retour(rev_head); est exécuté, qui renvoie &4 rev(&1);

• retour à la rev(&1)

liste en fonction est

NULL<-1(première) 2(deuxième)<-3<-4

et la valeur de rev_head est &4 qui a été adoptée par l'arrière(&3)

maintenant second- > suivant =premier est exécuté et liste devient

NULL<-1(premier) <- 2(deuxième)<-3<-4

retour(rev_head); est exécuté // rev_head=&4, qui a été retournée en arrière(&2) et la valeur de rev_head est passée à la fonction principale.

espérons que cette aide. Il m'a fallu beaucoup de temps pour comprendre cela et aussi à écrire cette réponse.

c'est une belle approche que l'on peut suivre pour inverser SLL récursivement:

1.    struct node* head; // global head
2.    void rec_reverse(struct node* prev, struct node* cur)
3.    {
4.        if (cur)
5.        {
6.            rec_reverse(cur, cur->next);
7.            cur->next = prev;
8.        }
9.        else
10.            head = prev;
11.    }

Appel de la fonction de cette manière:

rec_reverse(NULL, head);

Approche:

• appeler la fonction de façon récursive (ligne 6) Nous allons au dernier noeud de liste liée.
• puis on met à jour head avec l'adresse du dernier noeud (ligne 10).
• finalement, nous pointons le lien de chaque noeud à son noeud précédent (ligne 7).

    To fix head also:

void reverse_list_recursive_internal (struct list **head, struct list *node)
{
    /* last node, fix the head */
    if (node->next == NULL) {
        *head = node;
        return; 
    }
    reverse_list_recursive_internal(head, node->next);
    node->next->next = node;
    node->next = NULL;
}

void reverse_list_recursive (struct list **head)
{
    if (*head == NULL) {
        return;
    }
    reverse_list_recursive_internal(head, *head);
}

Il me semble que personne n'a proposé un algorithme qui est queue-récursive. En principe, un algorithme récursif peut être compilé sans pile (à condition que le compilateur soit suffisamment intelligent), produisant ainsi du code qui consomme moins de mémoire.

supposons TList est un type de données personnalisé pour une liste mono-liée, c'est un pointeur vers une structure qui comme un link champ pour accéder à l'élément suivant dans la liste.

l'algorithme est La suivantes:

``

TList reverse_aux(TList l, TList solution) {
    if (l == NULL) {
        return solution;
    } else {
        TList tmp = l->link;
        l->link = solution;
        return reverse_aux(tmp, l);
    }
}

TList reverse(TList l) {
    return reverse_aux(l, NULL);
}

``