#include <stdio.h>
struct ptr{
	int valor;
	struct ptr *prox, *ant;
};
struct ptr *inicio, *inicio2;
void inserir_ordenada(int valor){
	struct ptr *aux;
	if(inicio==(struct ptr *)NULL){
		inicio=(struct ptr *)malloc(sizeof(struct ptr));
		inicio->valor=valor;
		inicio->prox=(struct ptr *)NULL;
		inicio->ant=(struct ptr *)NULL;
	}else{
		aux=inicio;
		if(valor<aux->valor){
			aux->ant=(struct ptr *)malloc(sizeof(struct ptr));
			aux->ant->prox=aux;
			aux->ant->ant=(struct ptr *)NULL;
			aux->ant->valor=valor;
			aux=aux->ant;
			inicio=aux;
		}else{
			while(valor>aux->valor && aux->prox!=(struct ptr *)NULL){
				aux=aux->prox;
			}
			if(valor<aux->valor){
				aux->ant->prox=(struct ptr *)malloc(sizeof(struct ptr));
				aux->ant->prox->valor=valor;
				aux->ant->prox->ant=aux->ant;
				aux->ant->prox->prox=aux;
			}else{
				aux->prox=(struct ptr *)malloc(sizeof(struct ptr));
				aux->prox->valor=valor;
				aux->prox->ant=aux;
				aux->prox->prox=(struct ptr *)NULL;
				aux=aux->prox;
			}
		}
	}
}
void criar_crescente(){
	struct ptr *aux;
	inicio=(struct ptr *)NULL;
	int valor;
	printf("Digite o valor:");
	scanf("%d", &valor);
	while(valor>=0){
		inserir_ordenada(valor);
		printf("Digite o valor:");
		scanf("%d", &valor);
	}
}
void inserir_ordenada2(int valor){
	struct ptr *aux;
	if(inicio2==(struct ptr *)NULL){
		inicio2=(struct ptr *)malloc(sizeof(struct ptr));
		inicio2->valor=valor;
		inicio2->prox=(struct ptr *)NULL;
		inicio2->ant=(struct ptr *)NULL;
	}else{
		aux=inicio2;
		if(valor<aux->valor){
			aux->ant=(struct ptr *)malloc(sizeof(struct ptr));
			aux->ant->prox=aux;
			aux->ant->ant=(struct ptr *)NULL;
			aux->ant->valor=valor;
			aux=aux->ant;
			inicio2=aux;
		}else{
			while(valor>aux->valor && aux->prox!=(struct ptr *)NULL){
				aux=aux->prox;
			}
			if(valor<aux->valor){
				aux->ant->prox=(struct ptr *)malloc(sizeof(struct ptr));
				aux->ant->prox->valor=valor;
				aux->ant->prox->ant=aux->ant;
				aux->ant->prox->prox=aux;
			}else{
				aux->prox=(struct ptr *)malloc(sizeof(struct ptr));
				aux->prox->valor=valor;
				aux->prox->ant=aux;
				aux->prox->prox=(struct ptr *)NULL;
				aux=aux->prox;
			}
		}
	}
}
void criar_crescente2(){
	struct ptr *aux;
	inicio2=(struct ptr *)NULL;
	int valor;
	printf("Digite o valor:");
	scanf("%d", &valor);
	while(valor>=0){
		inserir_ordenada(valor);
		printf("Digite o valor:");
		scanf("%d", &valor);
	}
}
void juntar_lista(){
	struct ptr *aux;
	if(inicio2->valor<inicio->valor){
		inicio->ant=(struct ptr *)malloc(sizeof(struct ptr));
		inicio->ant->valor=inicio2->valor;
		inicio->ant->prox=inicio;
		inicio->ant->ant=(struct ptr *)NULL;
		inicio=inicio->ant;
	}else{
		aux=inicio;
		while(inicio2->valor>aux->valor && aux->prox!=(struct ptr*)NULL)
			aux=aux->prox;
		if(inicio2->valor<aux->valor){
			aux->ant->prox=(struct ptr *)malloc(sizeof(struct ptr));
			aux->ant->prox->valor=inicio2->valor;
			aux->ant->prox->ant=aux->ant;
			aux->ant->prox->prox=aux;
		}else{
			 aux->prox=(struct ptr *)malloc(sizeof(struct ptr));
			 aux->prox->ant=aux;
			 aux->prox->valor=inicio2->valor;
			 aux->prox->prox=(struct ptr *)NULL;
		}
	}
	inicio2=inicio2->prox;
}
void mostra(){
	struct ptr *aux;
    aux = inicio;
    if (inicio==(struct ptr *) NULL)
        printf ("Lista vazia!");
    else{
        printf ("Elementos da lista: ");
        while (aux!=(struct ptr *) NULL){
            printf ("%d", aux->valor);
            if (aux->prox!=(struct ptr *) NULL)
                printf ("->");
            aux = aux->prox;
		}
	}
}
main(){
	criar_crescente();
	criar_crescente2();
	juntar_lista();
	mostra();
}