Dada uma lista encadeada que armazena números inteiros, escreva uma função que transforma a lista dada em duas listas encadeadas: a primeira contendo os elementos cujo conteúdo é par e a segunda contendo os elementos com conteúdos impares

Passo 1

O enunciado pede uma função que, dada uma lista encadeada de inteiros, produza duas listas encadeadas: uma só com os valores pares e outra só com os valores ímpares. Vamos usar conceitos de lista simplesmente encadeada e teste de paridade usando operador módulo.

Passo 2

Primeiro, precisamos da definição do nó e do protótipo da função. Em C podemos fazer:
Definimos duas listas auxiliares (cabeças e caudas) para as listas de pares e ímpares, e as inicializamos como vazias (NULL).

Passo 3

Percorremos a lista original com um ponteiro ", atualizamos a cauda.

Passo 4

Depois de processar todos os nós, garantimos que as caudas de ambas as listas terminem em NULL.

Passo 5

Retornamos as duas novas listas via parâmetros de saída (ponteiros para ponteiro) no final da função.

Resposta

typedef struct Node {
int data;
struct Node *next;
} Node;
/**
  • splitList: divide a lista original em duas: pares e ímpares.
  • @head: cabeça da lista original.
  • @evenHead: ponteiro de saída para cabeça da lista de pares.
  • @oddHead: ponteiro de saída para cabeça da lista de ímpares.
    */
    void splitList(Node *head, Node **evenHead, Node **oddHead) {
    Node *evenTail = NULL;
    Node *oddTail = NULL;
    *evenHead = NULL;
    *oddHead = NULL;
    Node *current = head;
    while (current != NULL) {
    Node *nextNode = current->next;
    current->next = NULL;
    if (current->data % 2 == 0) {
    if (*evenHead == NULL) {
    *evenHead = current;
    evenTail = current;
    } else {
    evenTail->next = current;
    evenTail = current;
    }
    } else {
    if (*oddHead == NULL) {
    *oddHead = current;
    oddTail = current;
    } else {
    oddTail->next = current;
    oddTail = current;
    }
    }
    current = nextNode;
    }
    }

Exercícios relacionados