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).
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;
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;
}
}