Inversion récursive d'une liste chainée

Signaler
Messages postés
3
Date d'inscription
vendredi 23 avril 2004
Statut
Membre
Dernière intervention
30 avril 2007
-
Messages postés
3
Date d'inscription
vendredi 23 avril 2004
Statut
Membre
Dernière intervention
30 avril 2007
-
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.

3 réponses

Messages postés
987
Date d'inscription
mardi 31 mai 2005
Statut
Membre
Dernière intervention
30 août 2012
18
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
++
Messages postés
3
Date d'inscription
vendredi 23 avril 2004
Statut
Membre
Dernière intervention
30 avril 2007

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..
Messages postés
3
Date d'inscription
vendredi 23 avril 2004
Statut
Membre
Dernière intervention
30 avril 2007

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.