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

typedef struct node
{
  int x;
  int count;
  struct node *next;
} NODE;

typedef NODE *PNODE;

PNODE create_node(int);
PNODE insert_integer(PNODE, int);

int main(void)
{
  int x;
  PNODE pList = NULL, pTemp;

  printf("Enter numbers one at a time, EOF (Ctrl-D) to stop.\n");
  while(1)
  {
    if (scanf("%d", &x) == EOF)
      break;

    pList = insert_integer(pList, x);
  }

  printf("\nThe numbers in sorted order are:\n");
  for (pTemp = pList; pTemp != NULL; pTemp = pTemp->next)
  {
    for (x = 0; x < pTemp->count; x++)
      printf("%d\n", pTemp->x);
  }

  while (pList != NULL)
  {
    pTemp = pList->next;
    free(pList);
    pList = pTemp;
  }

  return 0;
}

/*
 * Creates a new node for the given data and returns a pointer to it.
 */
PNODE create_node(int x)
{
  PNODE pTemp;

  pTemp = (PNODE) malloc (sizeof(NODE));
  if (pTemp == NULL)
  {
    printf("Out of memory, could not store number!\n");
  }
  else
  {
    pTemp->x = x;
    pTemp->count = 1;
    pTemp->next = NULL;
  }

  return pTemp;
}

/*
 * Inserts integer x into pList, keeping list in sorted order.
 * If x is new, create a new node with count 1; otherwise, find the
 * the node corresponding to x an increase its count by 1.
 *
 * Returns a pointer to the head of the updated list (which changes
 * when a new integer is placed at the start of the list).
 */
PNODE insert_integer(PNODE pList, int x)
{
  PNODE pPrev, pCur, pNew;

  // Inserting pNew into an empty list, it just becomes the updated list
  if (pList == NULL)
  {
    pNew = create_node(x);
    return pNew;
  }

  // If x is less than pList->x, pNew becomes the start of the list
  if (x < pList->x)
  {
    pNew = create_node(x);
    pNew->next = pList;
    pList = pNew;
    return pList;
  }

  // Otherwise, find the position for x and put it there
  pPrev = NULL;
  pCur = pList;
  while ((pCur != NULL) && (pCur->x < x))
  {
    pPrev = pCur;
    pCur = pCur->next;
  }
  if ((pCur != NULL) && (pCur->x == x))
  {
    // Integer has occurred before, increase count
    pCur->count = pCur->count + 1;
  }
  else {
    // New integer goes between pPrev an pCur
    pNew = create_node(x);
    pNew->next = pCur;
    pPrev->next = pNew;
  }
  
  return pList;
}