#include<stdio.h>                       // pour printf
#include<stdlib.h>                      // pour malloc
typedef struct maillon maillon, *liste; //maillon=struct maillon  liste=struct maillon*
struct maillon { int val; liste suiv; };// Un maillon contient un entier VAL et
                                        // un pointeur SUIV sur le maillon suivant.
liste nouv(int val, liste suiv)
{ liste a=malloc(sizeof(maillon));// crée un nouveau maillon dont les deux champs sont
  *a=(maillon){val,suiv};         // initialisés avec les arguments de la fonction
  return a;                       // et rend un pointeur sur ce nouveau maillon.
}
#if 1                             // versions récursives de toutes les procédures
void aff(liste a)                         // Pour afficher une liste d'entiers on
{ if(a) printf(" %d",a->val),aff(a->suiv);// affiche le premier élément puis le reste.
  else  printf("\n");                     // Si elle est vide on passe à la ligne.
}
int longueur(liste a) { return a ? 1     +longueur(a->suiv) : 0 ; }
int somme   (liste a) { return a ? a->val+somme   (a->suiv) : 0 ; }
liste inserequeue(int x,liste a)
{return a             ? a->suiv=inserequeue(x,a->suiv),a : nouv(x,0) ;}
liste inseretrie (int x,liste a)
{return a && a->val<x ? a->suiv=inseretrie (x,a->suiv),a : nouv(x,a) ;}
liste fusion(liste a,liste b) // fusionne deux listes triées en une seule
{ return !a ? b :             // Si a est vide on rend b.
         !b ? a :             // Si b est vide on rend a.
         a->val<b->val ? a->suiv=fusion(a->suiv,b), a :
                       ( b->suiv=fusion(b->suiv,a), b ) ;
}
#else                  // versions itératives des fonctions récursives précédentes                 
void aff(liste a)
{ for(;a;a=a->suiv) printf(" %d",a->val);  // a parcourt la liste.
  printf("\n");                            // A la fin on passe à la ligne.
}
int longueur(liste a)
{ int l=0; 
  for(;a;a=a->suiv) l++;      // l augmente d'un pour chaque maillon 
  return l;
}
int somme   (liste a)
{ int l=0; 
  for(;a;a=a->suiv) l+=a->val;// l contient la somme des valeurs des premiers maillons
  return l;
}
liste inserequeue(int x,liste a)
{ liste *b=&a;            // *b est la liste au bout de laquelle on ajoutera x
  while(*b) b=&(*b)->suiv;// b vaut &a puis &(a->suiv) puis &(a->suiv->suiv) etc.
  *b=nouv(x,0);           // Quand *b vaut 0 on le remplace.
  return a;               // a pointe sur le premier maillon de l'ancienne liste
}                         // ou le nouveau maillon quand b pointe encore sur a
liste inseretrie (int x,liste a)
{ liste *b=&a;                 // comme la procédure précédente, mais b s'arrête dès
  while(*b && (*b)->val<x) b=&(*b)->suiv; // qu'on trouve l'endroit où
  *b=nouv(x,*b);                          // insérer le nouveau maillon.
  return a;
}
liste fusion(liste a,liste b)// On va faire a=fusion(a,b) puis on rendra a
{ liste *aa=&a, p;           // En fait on remplace *aa par la fusion de *aa et b.
  while(b) if(*aa && (*aa)->val<=b->val) aa=&(*aa)->suiv;   // *aa avance
           else                          p=*aa, *aa=b, b=p; // On échange *aa et b.
  return a;
}
#endif
liste trifusion(liste a)
{ liste b=0,c=0,p;
  while(a) p=a, a=p->suiv,      // on enlève les maillons en tête de a et on les met
           p->suiv=b, b=c, c=p; // alternativement dans b et c.
  return b ? fusion(trifusion(b),trifusion(c)) // on trie b et c puis on les fusionne
           : c;                 // Quand b est vide, c contient au plus un maillon
}
int main()
{ liste a=0, b=0, c=0;
  int i,x;
  for(i=0;i<10;i++) a=nouv(x=i*3%10*2,a), b=inserequeue(i*3,b), c=inseretrie(x,c);
  printf("insertion en tête  :"), aff(a);
  printf("insertion en queue :"), aff(b);
  printf("insertion triée    :"), aff(c);
  printf("En fusionnant les deux premières listes on obtient :"), aff(c=fusion(b,c));
  printf("La première liste a pour longueur  %d et pour somme  %d\n",
         longueur(a),somme(a));
  printf("En la triant on obtient :"), aff(a=trifusion(a));
  return 0;
}