#include <stdio.h>
#include <stdlib.h>
#define NULL 0
 
struct linked_list
{
 int number;
 struct linked_list *next;
};
typedef struct linked_list node;
 
main ()
{
 int n;
 node *head = NULL;
 void print(node *p);
 node *insert_Sort(node *p, int n);
 
 printf("Input the list of numbers.\n");
 printf("At end, type -999.\n");
 scanf("%d",&n);
 
 while(n != -999)
 {
  if(head == NULL)       /* create 'base' node */
  {
   head = (node *)malloc(sizeof(node));
   head ->number = n;
   head->next = NULL;
 
  }
 
  else    /* insert next item */
  {
   head = insert_Sort(head,n);
  }
  scanf("%d", &n);
 }
 printf("\n");
 print(head);
 print("\n");
}
node *insert_Sort(node *list, int x)
{
 node *p1, *p2, *p;
 p1 = NULL;
 p2 = list; /* p2 points to first node */
 
 for( ; p2->number < x ; p2 = p2->next)
 {
  p1 = p2;
 
  if(p2->next == NULL)
  {
   p2 = p2->next;    /* p2 set to NULL */
   break;      /* insert new node at end */
  }
 }
 
 /* key node found */
 p = (node *)malloc(sizeof(node)); /* space for new node */
 p->number = x;     /* place value in the new node */
 p->next = p2;      /* link new node to key node */
 if (p1 == NULL)
  list = p;      /* new node becomes the first node */
 else
  p1->next = p;  /* new node inserted after 1st node */
 return (list);
}
void print(node *list)
{
 if (list == NULL)
  printf("NULL");
 else
 {
  printf("%d-->",list->number);
  print(list->next);
 }
 return;
}