Continuando nosso Curso de Programação C, vamos resolver mais um exercício? Nesta aula vamos aprender como dividir uma lista encadeada em duas listas, uma lista par e uma lista ímpar.

Já sabemos como verificar se um número é par ou ímpar, basta verificar o resto da divisão por 2. Agora, o que precisamos é percorrer a lista e, para cada nó, verificar se o valor é par ou ímpar, se for par vamos inserir em uma lista par, se for ímpar vamos inserir em uma lista ímpar.

Para resolver este problema podemos desenvolver um procedimento que recebe como parâmetro três ponteiros pata três listas diferentes, a lista par, a lista ímpar e a lista a ser dividida.

/*
     Procedimento para dividir uma lista L nas listas P e I
*/
void dividir(No **L, No **P, No **I){
    No *aux = *L;
    while(aux){
        if(aux->valor > 0){ // se valor maior que zero
            if(aux->valor % 2 == 0) // se for par
                inserir_no_inicio(P, aux->valor);
            else
                inserir_no_inicio(I, aux->valor);
        }
        aux = aux->proximo;
    }
}

Perceba que já temos todos os outros os procedimento que precisamos. Se o valor for par basta chamar um dos procedimentos de inserção que já desenvolvemos passando a lista par e o valor par a ser inserido. Caso contrário, chamamos um dos procedimentos de inserção passando a lista ímpar e o valor ímpar a ser inserido.

Caso o valor não possa ser classificado como par ou ímpar, ou seja, se for menor ou igual a zero, então ele é desconsiderado e não é inserido em nenhuma das duas listas.

Código completo em C para dividir uma lista em Lista Par e Lista Ímpar

/*
            Código escrito por Wagner Gaspar
            Agosto de 2021

            Aula 255: Lista Simplesmente Encadeada
            Dividir uma lista L nas listas Par e Impar
*/

typedef struct no{
    int valor;
    struct no *proximo;
}No;

// procedimento para inserir no início
void inserir_no_inicio(No **lista, int num){
    No *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        novo->proximo = *lista;
        *lista = novo;
    }
    else
        printf("Erro ao alocar memoria!\n");
}

// procedimento para inserir no fim
void inserir_no_fim(No **lista, int num){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        novo->proximo = NULL;

        // é o primeiro?
        if(*lista == NULL)
            *lista = novo;
        else{
            aux = *lista;
            while(aux->proximo)
                aux = aux->proximo;
            aux->proximo = novo;
        }
    }
    else
        printf("Erro ao alocar memoria!\n");
}

// procedimento para inserir no meio
void inserir_no_meio(No **lista, int num, int ant){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        // é o primeiro?
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        }
        else{
            aux = *lista;
            while(aux->valor != ant && aux->proximo)
                aux = aux->proximo;
            novo->proximo = aux->proximo;
            aux->proximo = novo;
        }
    }
    else
        printf("Erro ao alocar memoria!\n");
}

void inserir_ordenado(No **lista, int num){
    No *aux, *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = num;
        // a lista está vazia?
        if(*lista == NULL){
            novo->proximo = NULL;
            *lista = novo;
        } // é o menor?
        else if(novo->valor < (*lista)->valor){
            novo->proximo = *lista;
            *lista = novo;
        }
        else{
            aux = *lista;
            while(aux->proximo && novo->valor > aux->proximo->valor)
                aux = aux->proximo;
            novo->proximo = aux->proximo;
            aux->proximo = novo;
        }
    }
    else
        printf("Erro ao alocar memoria!\n");
}

No* remover(No **lista, int num){
    No *aux, *remover = NULL;

    if(*lista){
        if((*lista)->valor == num){
            remover = *lista;
            *lista = remover->proximo;
        }
        else{
            aux = *lista;
            while(aux->proximo && aux->proximo->valor != num)
                aux = aux->proximo;
            if(aux->proximo){
                remover = aux->proximo;
                aux->proximo = remover->proximo;
            }
        }
    }
    return remover;
}

No* buscar(No **lista, int num){
    No *aux, *no = NULL;

    aux = *lista;
    while(aux && aux->valor != num)
        aux = aux->proximo;
    if(aux)
        no = aux;
    return no;
}

void dividir(No **L, No **P, No **I){
    No *aux = *L;
    while(aux){
        if(aux->valor > 0){
            if(aux->valor % 2 == 0)
                inserir_no_inicio(P, aux->valor);
            else
                inserir_no_inicio(I, aux->valor);
        }
        aux = aux->proximo;
    }
}

void imprimir(No *no){
    printf("\n\tLista: ");
    while(no){
        printf("%d ", no->valor);
        no = no->proximo;
    }
    printf("\n\n");
}

int main(){

    int opcao, valor, anterior;
    No *removido, *lista = NULL;
    No *Par = NULL, *Impar = NULL;

    do{
        printf("\n\t0 - Sair\n\t1 - InserirI\n\t2 - inserirF\n\t3 - InserirM\n\t4 - InserirO\n\t5 - Remover\n\t6 - Imprimir\n\t7 - Buscar\n\t8 - Dividir\n");
        scanf("%d", &opcao);

        switch(opcao){
        case 1:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_no_inicio(&lista, valor);
            break;
        case 2:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_no_fim(&lista, valor);
            break;
        case 3:
            printf("Digite um valor e o valor de referencia: ");
            scanf("%d%d", &valor, &anterior);
            inserir_no_meio(&lista, valor, anterior);
            break;
        case 4:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_ordenado(&lista, valor);
            break;
        case 5:
            printf("Digite um valor a ser removido: ");
            scanf("%d", &valor);
            removido = remover(&lista, valor);
            if(removido){
                printf("Elemento a ser removido: %d\n", removido->valor);
                free(removido);
            }
            else
                printf("Elemento inexistente!\n");
            break;
        case 6:
            printf("\nLista L:\n");
            imprimir(lista);
            printf("\nLista P:\n");
            imprimir(Par);
            printf("\nLista I:\n");
            imprimir(Impar);
            break;
        case 7:
            printf("Digite um valor a ser buscado: ");
            scanf("%d", &valor);
            removido = buscar(&lista, valor);
            if(removido)
                printf("Elemento encontrado: %d\n", removido->valor);
            else
                printf("Elemento nao encontrado!\n");
            break;
        case 8:
            dividir(&lista, &Par, &Impar);
            printf("\nDivisao realizada com sucesso!\n");
            break;
        default:
            if(opcao != 0)
                printf("Opcao invalida!\n");
        }

    }while(opcao != 0);

    return 0;
}