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

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

typedef NODE *PNODE;

PNODE create_node(int);
PNODE insert_node(PNODE, PNODE);
PNODE reverse_list(PNODE);

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;

    pTemp = create_node(x);
    if (pTemp != NULL)
    {
      pList = insert_node(pList, pTemp);
    }
  }

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

  // Reverse the list
  pList = reverse_list(pList);

  printf("\nThe numbers in reverse sorted order are:\n");
  for (pTemp = pList; pTemp != NULL; pTemp = pTemp->next)
  {
    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->next = NULL;
  }

  return pTemp;
}

/*
 * Inserts node pNew into pList, keeping list in sorted order.
 *
 * Returns a pointer to the head of the updated list (which changes
 * when the new item was placed at the start of the list).
 */
PNODE insert_node(PNODE pList, PNODE pNew)
{
  PNODE pPrev, pCur;

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

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

  // Otherwise, find the position for pNew and put it there
  pPrev = pList;
  pCur = pList->next;
  while ((pCur != NULL) && (pCur->x < pNew->x))
  {
    pPrev = pCur;
    pCur = pCur->next;
  }
  pNew->next = pCur;
  pPrev->next = pNew;

  return pList;
}

/*
 * Reverses the order of the nodes in a linked list.
 *
 * Returns a pointer to the updated list.
 */
PNODE reverse_list(PNODE pList)
{
  PNODE pPrev, pCur, pNext;

  if (pList == NULL)
    return NULL;

  pPrev = NULL;
  pCur = pList;
  do
  {
    pNext = pCur->next;
    pCur->next = pPrev;
    pPrev = pCur;
    pCur = pNext;
  } while (pCur != NULL);

  return pPrev;
}