inversion récursive d'une liste chainée

Question

bonjour il faudrait que je programme (~5-6 lignes) une fonction récursive pour inverser une liste chainée !!
Mais je ne trouve pas la façon pour y procéder!! Pourriez vous m'aider svp, voici mon code:

"import java.util.LinkedList;

class ListeChainee{ 
    int valeur;
    ListeChainee suivant;

    ListeChainee(int i, ListeChainee l) {
        valeur = i;
        suivant = l;
    }

    static void imprimer(ListeChainee l) {
        while (l != null) {
            System.out.print(l.valeur+ " ");
            l = l.suivant;
        }
    }

//    static ListeChainee Renverser(ListeChainee l) {
//       // version itérative
//        ListeChainee l1 = null;
//        while (l!=null)     {
//            l1 = new ListeChainee (l.valeur,l1);
//            l= l.suivant;            
//        }        
//        return l1;
//    }

    static ListeChainee Renverser(ListeChainee l) {
           // version récursive    
        if (l!=null) {  
            
            l.suivant = Renverser(l.suivant);    
            
        }
        return l;
        
        }
    
    public static void main(String[] args) {
        ListeChainee test = new ListeChainee(12, new ListeChainee(34, new ListeChainee(56, null)));
        ListeChainee.imprimer(test);
        System.out.println();
        ListeChainee.imprimer(Renverser(test));
    }
}"

Merci pour votre aide,
cordialement vivi120.

cs_laurent1024 · Answer

Inverser une liste chaine récursivement c'est mettre le premier élément a la fin de la liste chaine, et appeller l'inversion de la liste chainé sur les les autres éléments de la liste chaine 
 A B C D E F  => inverser (B C D E F) + A
                       => inverser(inverser(C D E F) + B) +A
                       => inverser(inverser(inverser(D E F) + C) +B) + A
                             => ...

voila j'espere que cela va t"aider
++

cs_vivi120 · Answer

Bonjour laurent, 
j'ai réussi à inverser ma liste chaînée de façon itérative (cf première réponse), mais je ne sais pas comment implémanter la fonction inverser(liste chainéee l) de façon récursive! Regarde le code que j'ai mis ci dessus tu comprendra tout de suite!
En tout cas, merci de ton aide..

cs_vivi120 · Answer

j'ai trouvé ce que je cherchais!
Alors il suffisait de rajouter en paramètre une autre liste chainée initialiséé à null au départ.

voici la forme récursive :

static ListeChainee Renverser(ListeChainee l,ListeChainee l1) {
           // version récursive                        
        if (l!=null) {    
          return Renverser(l.suivant,new ListeChainee (l.valeur,l1));
        }
        return l1;        
    }

Voila, @ très bientôt.

Inversion récursive d'une liste chainée

3 réponses

Votre réponse

Discussions similaires