Implemente uma função recursiva para verificar se duas listas dinâmicas e encadeadas são iguais.
Passo 1
O enunciado pede para escrever uma função recursiva que verifique se duas listas encadeadas dinâmicas são iguais, ou seja, que tenham os mesmos valores na mesma ordem. Vamos trabalhar com listas ligadas simples, onde cada nó tem um campo de dado (por exemplo, um inteiro) e um ponteiro para o próximo nó.
Passo 2
Precisamos definir os casos-base da recursão. Se os dois ponteiros de lista forem NULL ao mesmo tempo, chegamos ao fim das duas listas simultaneamente e podemos dizer que são iguais. Se apenas um deles for NULL, uma lista é mais curta que a outra e não são iguais.
Passo 3
Se chegamos aqui e nenhum dos ponteiros é NULL, comparamos o valor armazenado em cada nó. Se esses valores forem diferentes, retornamos false imediatamente, pois as listas diferem em pelo menos uma posição.
Passo 4
Se os valores do nó atual forem iguais, fazemos a chamada recursiva passando os ponteiros para o próximo nó de cada lista. O resultado dessa chamada é o resultado final da função.
Passo 5
Implementamos então a função, por exemplo em C, usando a lógica descrita:
// Definição de nó para lista encadeada simples
typedef struct Node {
int data;
struct Node *next;
} Node;
// Função recursiva que retorna true se as duas listas forem iguais
bool lists_are_equal(Node *l1, Node *l2) {
// Caso-base: ambas vazias
if (l1 == NULL && l2 == NULL)
return true;
// Caso-base: apenas uma vazia
if (l1 == NULL || l2 == NULL)
return false;
// Compara o valor do nó atual
if (l1->data != l2->data)
return false;
// Chamada recursiva para os próximos nós
return lists_are_equal(l1->next, l2->next);
}
Resposta
// Função recursiva que verifica se duas listas encadeadas são iguais
bool lists_are_equal(Node *l1, Node *l2) {
if (l1 == NULL && l2 == NULL)
return true;
if (l1 == NULL || l2 == NULL)
return false;
if (l1->data != l2->data)
return false;
return lists_are_equal(l1->next, l2->next);
}