Implemente uma função não recursiva para verificar se duas listas dinâmicas e encadeadas são iguais.
Passo 1
Neste exercício, queremos implementar uma função não recursiva que verifica se duas listas dinâmicas e encadeadas são iguais. Isso cai na matéria de Estruturas de Dados, mais especificamente no tópico de listas ligadas. Para resolver, vamos precisar percorrer ambas as listas simultaneamente e comparar seus elementos um a um.
Passo 2
Duas listas são consideradas iguais quando têm o mesmo número de nós e os valores armazenados em cada nó correspondente são idênticos. Se em algum ponto encontrarmos valores diferentes, podemos concluir imediatamente que as listas não são iguais.
A estratégia não recursiva consiste em usar dois ponteiros, um para cada lista (por exemplo, p1 e p2). Enquanto ambos os ponteiros não forem nulos, comparamos
e
. Se eles diferirem, retornamos falso; caso contrário, avançamos os dois ponteiros para o próximo nó.
Passo 3
Quando o laço terminar, se ambos os ponteiros tiverem chegado ao final (ou seja, ambos forem nulos), as listas têm o mesmo comprimento e todos os valores correspondentes conferem, então retornamos verdadeiro. Caso contrário, uma lista é maior que a outra e retornamos falso.
Passo 4
Abaixo está a implementação em C da função que verifica a igualdade das listas de forma iterativa:
Resposta
#include <stdbool.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
bool listasIguais(Node *l1, Node *l2) {
Node *p1 = l1;
Node *p2 = l2;
while (p1 != NULL && p2 != NULL) {
if (p1->data != p2->data) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
// Retorna true somente se ambas tiverem mesmo comprimento
return (p1 == NULL && p2 == NULL);
}