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

#define LIST_SIZE 150

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

node *createList ( int n )
{
   node *head, *p;
   int i;

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

   /* Create the dummy node */
   head = (node *)malloc(sizeof(node));
   head -> data = 0;

   /* Initialize the running pointer p */
   p = head;

   /* Node creation loop */
   for (i=0; i<n; ++i) {
      /* Create the next node */
      p -> next = (node *)malloc(sizeof(node));
      p = p -> next;
      p -> data = 1 + rand() % 999;
   }

   /* Terminate the list */
   p -> next = NULL;

   return head;
}

void printList ( node *head , char prompt[] )
{
   node *p;
   int i = 0;

   printf("%s", prompt);
   p = head -> next;
   while ( p != NULL ) {
      printf("%3d ", p -> data);
      p = p -> next;
      if (++i == 20) { printf("\n"); i = 0; }
   }
   if (i) printf("\n");
}

void insSort ( node *head )
{
   node *p, *q, *last;
   int t;

   if ((head == NULL)                          /* Uninitialized list */
      || (head -> next == NULL)                /* Empty list */
      || (head -> next -> next == NULL))       /* List of one element */
      return;

   /* The pointer last is used to locate the next element to insert.
      last -> next -> data is to be inserted in the proper place. */
   last = head -> next;

   /* When there are more elements to insert */
   while (last -> next != NULL) {
      /* t is to be inserted in the proper place */
      t = last -> next -> data;

      /* Find out the correct insertion position */
      p = head;
      while (p -> next -> data < t) p = p -> next;

      /* Here p points to the node after which t is to be inserted. */

      /* if p equals last, then t is already in the proper place. */
      if (p == last) last = last -> next;
      else {
         /* First remove the node containing t temporarily from the list */
         q = last -> next;
         last -> next = q -> next;

         /* Insert the removed node after the node pointed by p */
         q -> next = p -> next;
         p -> next = q;
      }
   }
}

int main ()
{
   node *head;

   head = createList(LIST_SIZE);
   printList(head,"\nThe list before sorting\n-----------------------\n");
   insSort(head);
   printList(head,"\nThe list after sorting\n----------------------\n");
}