#include<stdio.h>
#include<stdlib.h>
typedef struct element element, *pelement;
typedef struct { pelement tete, queue; } liste, *pliste;
struct element { int entier; pelement suivant; };
pelement nouv(int x)
{ pelement e=malloc(sizeof(*e));
  e->entier=x;
  return e;
}
void insertiontete(pliste l,pelement e)
{ if(!l->tete) l->queue=e;
  e->suivant=l->tete;
  l->tete=e;
}
void insertionqueue(pliste l,pelement e)
{ if(l->tete) l->queue->suivant=e;
  else l->tete=e;
  e->suivant=0;
  l->queue=e;
}
pelement suppressiontete(pliste l)
{ pelement e=l->tete;
  l->tete=e->suivant;
  return e;
}
pelement fusion1(pelement a, pelement b)
{ return !a? b :
         !b? a :
         a->entier<b->entier? a->suivant=fusion1(a->suivant,b), a :
                            ( b->suivant=fusion1(b->suivant,a), b );
}
pelement fusion2(pelement a, pelement b)
{ pelement *c=&a;
  while(b)
  if(*c && (*c)->entier<=b->entier) c=&(*c)->suivant; else
  { pelement d=*c; *c=b, b=d; }
  return a;
}
#define fusion fusion2
pelement trifusion(pelement a)
{ pelement b=0, c=0;
  while(a) { pelement x=a; a=x->suivant, x->suivant=b, b=c, c=x; }
  return b? fusion(trifusion(b),trifusion(c)) : c;
}
void aff(pelement a)
{ for(;a;a=a->suivant) printf("%d ",a->entier); }
void affln(pelement a)
{ aff(a); printf("\n"); }
pelement dernier(pelement a)
{ if(a) while(a->suivant) a=a->suivant;
  return a;
}
void tri(pliste a)
{ a->queue=dernier(a->tete=trifusion(a->tete)); }
void libere(pliste a)
{ while(a->tete) free(suppressiontete(a)); }
int main()
{ liste a={0};
  int x;
  for(x=0;x<20;x++) (x&2?insertiontete:insertionqueue)(&a,nouv(x*17%37));
  affln(a.tete);
  tri(&a);
  affln(a.tete);
  for(x=0;x<10;x++) a.tete->entier++, insertionqueue(&a,suppressiontete(&a));
  affln(a.tete);
  libere(&a);
  return 0;
}