#include<stdio.h>                                    // Pour printf
#include<stdlib.h>                                   // Pour malloc

typedef struct maillon maillon, *liste;              //  maillon = struct maillon    liste= maillon* 
        struct maillon { int val; liste suiv; };     // Un maillon contient un entier et un pointeur sur le maillon suivant.

typedef struct{ liste tete,queue; } lliste;          //  tete et queue pointent sur le premier et le dernier maillon d'une même liste.

void aff(liste l)                                    // Pour afficher une liste chaînée,
{ for(;l;l=l->suiv) printf("%d ",l->val);            //   pour chacun de ses maillons on affiche la valeur qu'il contient.
  printf("\n");                                      //  On passe à la ligne une seule fois à la fois de la liste.
}

int somme(liste l)                                   // somme des éléments de la liste l
{ int s=0;
  for(;l;l=l->suiv) s+=l->val;
  return s;
}

liste inseretete(liste l,int x)                      // Pour insérer l'entier x en tête d'une liste l,
{ liste a=malloc(sizeof(*a));                        //  on crée un nouveau maillon
  *a=(maillon){x,l};                                 //   dans lequel on met x et l
  return a;                                          // La nouvelle liste est représentée par le pointeur sur ce nouveau maillon
}

liste inserequeue(liste l,int x)                     // On veut insérer l'entier x à la fin de la liste l.
{ liste p=l,q=inseretete(0,x);                       //  q est une nouvelle liste de longueur 1 formé d'un nouveau maillon contenant x
  if(!p) return q;                                   // Si l était vide, on rend cette nouvelle liste.
  while(p->suiv) p=p->suiv;                          // p avance jusqu'au dernier maillon.
  p->suiv=q;                                         // On met le nouveau maillon derrière le dernier.
  return l;                                          // La liste est toujours représentée par le pointeur sur le même premier maillon.
}

void inseretete2(lliste *a,int x)                    // On veut insérer l'entier x en tête de liste.
{ if(a->tete)          a->tete=inseretete(a->tete,x);// Si la liste n'était pas vide, son dernier maillon reste le même.
  else        a->queue=a->tete=inseretete(a->tete,x);// Si elle était vide le nouveau maillon est à la fois le premier et le dernier.
}

void inserequeue2(lliste *a,int x)                    // On veut insérer l'entier x en queue de liste.
{ if(a->tete) a->queue=a->queue->suiv=inseretete(0,x);// Si la liste n'était pas vide, son prenier maillon reste le même.
  else        a->queue=a->tete       =inseretete(0,x);// Si elle était vide le nouveau maillon est à la fois le premier et le dernier.
}

liste triselection(liste l)                           // On veut trier la liste l en gardant les mêmes maillons dans un autre ordre.
{ if(l)                                               // Si la liste est vide, elle est déjà triée. Il n'y a rien à faire.
  { liste pp=0, m=l, q;                               // m sera le maillon contenant le plus petit entier. pp sera le maillon précédent. 
    for(q=l;q->suiv;q=q->suiv)                        // q décrit tous les maillons sauf le dernier, donc q->suiv les décrit tous sauf le premier. 
      if(q->suiv->val<m->val)  pp=q, m=q->suiv;       // Si q->suiv est un plus petit maillon, on le garde dans m en mettant à jour pp.
    if(pp) pp->suiv=m->suiv, m->suiv=l, l=m;          // Si le plus petit maillon n'est pas le premier, on le met en tête.
    l->suiv=triselection(l->suiv);                    // On trie la liste qui suit le premier maillon.
  }
  return l;                                           // l a peut-être changé, si le plus petit maillon n'était pas le premier.
}

liste fusion(liste a,liste b)                         // On veut fusionner les deux listes a et b qui sont déjà triées.
{ return !a ? b :                                     // Si a est vide le résultat est b.
         !b ? a :                                     // Si b est vide le résultat est a.
         a->val<=b->val ? a->suiv=fusion(a->suiv,b), a :// On met derrière le premier maillon de a ce qu'il faut. Puis on rend ce premier maillon.
         fusion(b,a);                                 // On inverse les rôles de a et b, donc on aura bien a->val<=b->val.
}

void fusion2(liste a,liste b,liste *c)                // *c=fusion(a,b)
{ if(!a) *c=b; else
  if(!b) *c=a; else
  if(a->val<b->val) *c=a, fusion2(a->suiv,b,&a->suiv);
  else              *c=b, fusion2(b->suiv,a,&b->suiv);
}

void fusion3(liste a,liste b,liste *c)                // comme fusion2 mais itérative
{ for(;a && b;)
  if(a->val<b->val) *c=a, c=&a->suiv, a=a->suiv; 
  else              *c=b, c=&b->suiv, b=b->suiv; 
  *c=a ? a : b;
}

liste fusion4(liste a,liste b)                        // comme fusion3 mais avec l'interface de fusion
{ liste r, *c=&r;
  for(;a && b;)
  if(a->val<b->val) *c=a, c=&a->suiv, a=a->suiv; 
  else              *c=b, c=&b->suiv, b=b->suiv; 
  *c=a ? a : b;
  return r;
}

liste trifusion(liste l)                              // On veut trier la liste l
{ liste a=0, b=0, p;                                  // a et b sont deux listes initialement vides.
  while(l) p=l, l=p->suiv, p->suiv=a, a=b, b=p;       // On répartit les maillons de l alternativement dans a et b.  |b]=|a| ou |b|=|a|+1
  return a ? fusion4(trifusion(a),trifusion(b)) : b;   // Si a est vide, alors b est de longueur 0 ou 1, donc triée. Sinon on trie a et b puis
}                                                     //   on les fusionne.

liste trifusion2(liste l)
{ int i,longueur=0;
  liste p,b;
  for(p=l;p;p=p->suiv) longueur++;                    // On compte les maillons de la liste.
  if(longueur<2) return l;                            // S'il y en a moins de deux, la liste est déjà triée.
  for(p=l,i=longueur/2-1;i;i--) p=p->suiv;            // On veut couper la liste en deux morceaux de longueur longueur/2 et longueur-longueur/2
  b=p->suiv;                                          // p est le dernier maillon de la première liste l, b le premier de la deuxième.
  p->suiv=0;                                          // On coupe la fin de l.
  fusion3(trifusion2(b),trifusion2(l),&l);            // On trie les deux listes puis on les fusionne.
  return l;
}

int main()
{ liste a=0;
  lliste b={0};
  int i;
  for(i=0;i<10;i++) a=inseretete(a,i*3%10);
  aff(a);
  printf("La somme est %d\n",somme(a));
  a=triselection(a);
  aff(a);
  for(i=21;i<=30;i++) a=inserequeue(a,-i);
  aff(a);
  a=trifusion2(a);
  aff(a);
  for(i=0;i<10;i++) inseretete2(&b,i*3%10);
  aff(b.tete);
  for(i=21;i<=30;i++) inserequeue2(&b,i);
  aff(b.tete);
  return 0;
}