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

typedef struct Elemento {
	int valor;
	struct Elemento*prox;
} Elemento;

typedef struct Lista {
	Elemento*Inicio;
	Elemento*Fim;
} Lista;

Lista*CriandoLista() {
	Lista*lista=(Lista*)malloc(sizeof(Lista));
	lista->Inicio=NULL;
	lista->Fim=NULL;
	return lista;
}

Elemento*CriandoElemento(int n) {
	Elemento*novo=(Elemento*)malloc(sizeof(Elemento));
	novo->prox=NULL;
	novo->valor=n;
	return novo;
}

void AddLista(Lista*lista,Elemento*novo) {
	if(lista->Inicio==NULL) {
		lista->Inicio=novo;
		lista->Fim=lista->Inicio;
	} else {
		lista->Fim->prox=novo;
		lista->Fim=novo;
	}
}

void Imprimir(Lista*lista) {
	Elemento*aux=lista->Inicio;
	while(aux!=NULL) {
		printf(" %d ",aux->valor);
		aux=aux->prox;
	}
	printf("\n");
}

void AddOrdenado(Lista*nvlista, Elemento* elemento) {
    if (nvlista->Inicio == NULL){
        nvlista->Inicio = nvlista->Fim = elemento;
        return;
    }

	Elemento *atual = nvlista->Inicio;
	Elemento *anterior = NULL;
    while (atual != NULL && atual->valor < elemento->valor){
        anterior = atual;
        atual = atual->prox;
    }

    if (atual == NULL){ //novo maior que todos
        nvlista->Fim->prox = elemento;
        nvlista->Fim = elemento;
    }
    else {
        if (anterior == NULL){
            elemento->prox = nvlista->Inicio;
            nvlista->Inicio = elemento;
        }
        else {
            elemento->prox = anterior->prox;
            anterior->prox = elemento;
        }
    }
}
void Ordenar(Lista*lista) {
	Lista*nvlista=CriandoLista();
	Elemento *no_atual = lista->Inicio;
	while(no_atual != NULL) {
        Elemento *novo = CriandoElemento(no_atual->valor);
		AddOrdenado(nvlista, novo);
		no_atual = no_atual->prox;
	}
	Imprimir(nvlista);
}

int main() {
	Lista*lista=CriandoLista();
	int n[]= {5,10,9,1,4,2,14,21,7};
	for(int i=0; i<sizeof(n)/sizeof(int); i++) {
		AddLista(lista,CriandoElemento(n[i]));
	}
	Imprimir(lista);
	Ordenar(lista);
}