#include<stdio.h>
#include<stdlib.h>
typedef struct chainon chainon, *liste;
struct chainon { int clef; liste suivant; };
liste fusion(liste a, liste b)
{ if(!a) return b;
  if(!b) return a;
  if(a->clef<=b->clef) return a->suivant=fusion(a->suivant,b), a;
  else                 return b->suivant=fusion(b->suivant,a), b;
}
void fusion2(liste a, liste b, liste *l)
{ if(!a) *l=b; else
  if(!b) *l=a; else
  if(a->clef<=b->clef) fusion2(a->suivant,b,&a->suivant), *l=a;
  else                 fusion2(b->suivant,a,&b->suivant), *l=b;
}
void fusion3(liste a, liste b, liste *l)
{ while(a&&b)
  if(a->clef<=b->clef) *l=a, l=&a->suivant, a=a->suivant;
  else                 *l=b, l=&b->suivant, b=b->suivant;
  *l=a?a:b;
}
liste fusion4(liste a, liste b)
{ liste c, *l=&c;
  while(a&&b)
  if(a->clef<=b->clef) *l=a, l=&a->suivant, a=*l;
  else                 *l=b, l=&b->suivant, b=*l;
  *l=a?a:b;
  return c;
}
liste fusion5(liste a, liste b)
{ liste c, *l=&a;
  while(b)
  if((c=*l) && c->clef<=b->clef) l=&c->suivant;
  else *l=b, b=c;
  return a;
}
liste tri(liste l)
{ liste a=0, b=0;
  while(l) { liste x=l; l=x->suivant, x->suivant=a, a=b, b=x; }
  if(!a) return b;
  if(1)  return fusion5(tri(a),tri(b));
  fusion2(tri(a),tri(b),&l); return l; 
}
liste nouv(int clef, liste suivant)
{ liste l=malloc(sizeof(*l));
  l->clef=clef;
  l->suivant=suivant;
  return l;
}
void aff(liste l)
{ if(l) printf("%d ",l->clef), aff(l->suivant);
  else  printf("\n");
}
liste eipoc(liste l) 
{ liste a=0;
  for(;l;l=l->suivant) a=nouv(l->clef,a);
  return a;
}
liste retourne(liste l)
{ liste a=0, x;
  while(l) x=l, l=x->suivant, x->suivant=a, a=x; 
  return a;
}
#if 0
int longueur(liste l) { return l?         1+longueur(l->suivant) :0; }
int somme   (liste l) { return l?      l->clef+somme(l->suivant) :0; }
liste copie (liste l) { return l? nouv(l->clef,copie(l->suivant)):0; }
#else
int longueur(liste l)
{ int s=0;
  for(;l;l=l->suivant) s++;
  return s;
}
int somme(liste l)
{ int s=0;
  for(;l;l=l->suivant) s+=l->clef;
  return s;
}
liste copie (liste l) { return retourne(eipoc(l)); }
#endif

liste copie2(liste a)
{ liste b=0, *l=&b;
  for(;a;a=a->suivant) *l=nouv(a->clef,0), l=&(*l)->suivant;
  return b;
}
int main()
{ liste l=nouv(5,nouv(2,nouv(3,0)));
  aff(l);
  l=tri(l);
  aff(l);
  int i;
  for(i=10;i--;) l=nouv(i*i%19,l);
  aff(l);
  l=tri(l);
  aff(l);
  printf("somme=%d longueur=%d\n",somme(l),longueur(l));
  liste a=copie2(l);
  aff(a);
  l=fusion(a,l);
  aff(l);
  l=retourne(l);
  aff(l);
  l=tri(l);
  aff(l);
  return 0;
}