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

struct celula {
    int conteudo;
    struct celula *seg;
};
typedef struct celula cel;

void inserir(int x, cel **lst);
void destruir(cel *p);
void mostrarLista(cel *lst);
void buscaMenor(cel **lst, cel ***menor);
int buscaMenor_Remove(cel **lst);

int main() {

    printf("Teste 1: Lista em ordem decrescente\n");
    cel *lst1 = NULL;
    inserir(9, &lst1);
    inserir(4, &lst1);
    inserir(2, &lst1);
    inserir(-1, &lst1);
    mostrarLista(lst1);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst1));
    mostrarLista(lst1);
    destruir(lst1);

    printf("\nTeste 2: Lista em ordem crescente\n");
    cel *lst2 = NULL;
    inserir(-5, &lst2);
    inserir(2, &lst2);
    inserir(9, &lst2);
    inserir(21, &lst2);
    mostrarLista(lst2);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst2));
    mostrarLista(lst2);
    destruir(lst2);

    printf("\nTeste 3: Lista fora de ordem com menor no final\n");
    cel *lst3 = NULL;
    inserir(15, &lst3);
    inserir(21, &lst3);
    inserir(9, &lst3);
    inserir(-5, &lst3);
    mostrarLista(lst3);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst3));
    mostrarLista(lst3);
    destruir(lst3);

    printf("\nTeste 4: Lista fora de ordem com menor no inicio\n");
    cel *lst4 = NULL;
    inserir(-6, &lst4);
    inserir(15, &lst4);
    inserir(21, &lst4);
    inserir(9, &lst4);
    mostrarLista(lst4);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst4));
    mostrarLista(lst4);
    destruir(lst4);

    printf("\nTeste 5: Lista fora de ordem com menor no meio\n");
    cel *lst5 = NULL;
    inserir(15, &lst5);
    inserir(-6, &lst5);
    inserir(21, &lst5);
    inserir(-8, &lst5);
    inserir(9, &lst5);
    inserir(4, &lst5);
    mostrarLista(lst5);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst5));
    mostrarLista(lst5);
    destruir(lst5);

    printf("\nTeste 6: Lista fora de ordem com menor no meio e repetido\n");
    cel *lst6 = NULL;
    inserir(15, &lst6);
    inserir(-8, &lst6);
    inserir(21, &lst6);
    inserir(-8, &lst6);
    inserir(9, &lst6);
    inserir(4, &lst6);
    mostrarLista(lst6);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst6));
    mostrarLista(lst6);
    destruir(lst6);

    printf("\nTeste 7: Lista unitaria\n");
    cel *lst7 = NULL;
    inserir(44, &lst7);
    mostrarLista(lst7);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst7));
    mostrarLista(lst7);
    destruir(lst7);

    printf("\nTeste 8: Lista vazia\n");
    cel *lst8 = NULL;
    mostrarLista(lst8);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst8));
    mostrarLista(lst8);
    destruir(lst8);

    printf("\nTeste 9: Lista com todos os elementos iguais\n");
    cel *lst9 = NULL;
    inserir(15, &lst9);
    inserir(15, &lst9);
    inserir(15, &lst9);
    inserir(15, &lst9);
    mostrarLista(lst9);
    printf("Conteudo: %d\n", buscaMenor_Remove(&lst9));
    mostrarLista(lst9);
    destruir(lst9);

    return 0;
}

void mostrarLista(cel *lst) {
    if (lst == NULL) {
        printf("NULL\n");
    } else {
        printf("%d->", lst->conteudo);
        mostrarLista(lst->seg);
    }
}

void inserir(int x, cel **lst) {
    cel *nova = (cel*) malloc(sizeof(cel*));
    nova->conteudo = x;
    nova->seg = NULL;
    cel *p = *lst;
    if (p == NULL) {
        *lst = nova;
    } else {
        while (p->seg != NULL) {
            p = p->seg;
        }
        p->seg = nova;
    }
}

void destruir(cel *lst) {
    if (lst == NULL) return;
    cel *p = lst->seg;
    free(lst);
    destruir(p);
}

void buscaMenor(cel **lst, cel ***menor) {
    if ((*lst) == NULL) return;
    if ((*lst)->conteudo < (**menor)->conteudo) *menor = lst;
    buscaMenor(&(*lst)->seg, menor);
}

int buscaMenor_Remove(cel **lst) {
    if (*lst == NULL) {
        printf("Lista Vazia!\n");
        return 0;
    }

    cel **menor = lst;
    buscaMenor(lst, &menor);
    cel *p = *menor;
    if (menor == lst) *lst = p->seg;
    *menor = p->seg;
    int v = p->conteudo;
    free(p);
    return v;
}