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 p1->data e p2->data. 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);
}

Exercícios relacionados