#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 25

typedef struct _node {
   int data;
   struct _node *next;
} node;

typedef struct {
   int size;
   node *head;
} list;

list init ( )
{
   list L;

   L.size = 0;

   /* Create dummy node */
   L.head = (node *)malloc(sizeof(node));
   L.head -> data = 0;
   L.head -> next = NULL;

   return L;
}

int empty ( list L )
{
   return (L.size == 0);
}

void print ( list L )
{
   node *p;

   p = L.head -> next;
   while (p != NULL) {
      printf("%d ", p -> data);
      p = p -> next;
   }
   printf("\n");
}

list insert ( list L, int n )
{
   node *p, *q, *r;

   /* Locate position of insertion */
   p = L.head;
   while ((p -> next != NULL) && (p -> next -> data < n)) p = p -> next;

   /* Insert freshly allocated node */
   q = p -> next;
   r = (node *)malloc(sizeof(node));
   r -> next = q;
   r -> data = n;
   p -> next = r;

   ++L.size;

   return L;
}

list delete ( list L )
{
   node *p, *q;
   int shift;

   if (!empty(L)) {
      /* Go to the correct deletion position */
      shift = (L.size - 1) / 2;
      p = L.head;
      while (shift--) p = p -> next;


      if (L.size % 2) {  /* Delete one element */
         q = p -> next;
         p -> next = q -> next;
         free(q);
         --L.size;
      } else {           /* Delete two elements */
         q = p -> next;
         p -> next = q -> next -> next;
         free(q -> next);
         free(q);
         L.size -= 2;
      }
   }
   return L;
}

int main ()
{
   list L;
   int i;

   srand((unsigned int)time(NULL));

   L = init();
   for (i=0; i<N; ++i) {
      L = insert(L, 100 + rand() % 900);
      print(L);
   }

   while (!empty(L)) {
      L = delete(L);
      print(L);
   }

   exit(0);
}