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

struct node {
  int info;
  struct node *next;
};

typedef struct node Node;

Node* createNode(int i, Node *next)
{
  Node* newNode = (Node *)malloc(sizeof(Node));
  newNode->info = i;
  newNode->next = next;
  return newNode;
}


Node* orderedInsert(Node* head, int i)
{

  if (head == NULL)
    return createNode(i, NULL);

  if (i < head->info)
    return createNode(i, head);

  Node* prev = head;
  Node* curr = head->next;

  while ((curr != NULL) && (i > curr->info))
  {
    prev = curr;
    curr = curr->next;
  }
  prev->next = createNode(i, curr);
  return head;
}

void printList(Node* head)
{
  printf("==================\n");
  while (head != NULL) 
  {
    printf("%d\n", head->info);
    head = head->next;
  } 
}


int main(void)
{

  Node* head = createNode(7,NULL);
  head = createNode(5,head);
  head = createNode(2,head);

  printList(head);

  head = orderedInsert(head, 1);

  printList(head);

  head = orderedInsert(head, 13);

  printList(head);

  head = orderedInsert(head, 8);

  printList(head);

  return 0;
}