Dadas duas listas encadeadas e dinâmicas L1 e L2, sem elementos repetidos, implemente a operação INTER, que cria uma terceira lista L3 com a intersecção entre as duas listas, também sem elementos repetidos

Passo 1

Beleza, o enunciado pede pra gente pegar duas listas encadeadas L1 e L2 sem elementos repetidos, e criar uma terceira lista L3 contendo apenas os elementos que aparecem nas duas (interseção), também sem repetição. O conteúdo envolve listas dinâmicas, busca de elemento e inserção de nós no fim.

Passo 2

Vamos definir a estrutura de nó e de lista em C pra ficar mais claro. O nó tem um valor inteiro e ponteiro pro próximo. Se a gente quer inserir rápido no fim, também guardamos ponteiro pro tail na lista.

Passo 3

Pra montar a interseção, precisamos de duas funções auxiliares: (1) search(List* L, int x) que percorre L e devolve ponteiro pro nó onde val==x ou NULL; e (2) append(List* L, int x) que cria um nó novo com x e adiciona no fim de L ajustando head/tail.

Passo 4

Com essas ferramentas, basta criar L3 vazia, percorrer cada elemento de L1 e, pra cada valor v, usar search em L2. Se search retornar não-NULL, chamamos append(L3, v). Como L1 não tem repetidos, a gente não precisa checar duplicata em L3.

Passo 5

Depois de rodar esse laço, L3 vai conter exatamente a interseção sem duplicatas. A complexidade fica em O(|L1|·|L2|), já que pra cada elemento de L1 a gente faz busca em L2.

Resposta

typedef struct Node { int val; struct Node* next; } Node;
typedef struct List { Node* head; Node* tail; } List;
#include <stdlib.h>
List* createList() {
List* L = (List*)malloc(sizeof(List));
L->head = L->tail = NULL;
return L;
}
Node* search(List* L, int x) {
Node* p = L->head;
while § {
if (p->val == x)
return p;
p = p->next;
}
return NULL;
}
void append(List* L, int x) {
Node* novo = (Node*)malloc(sizeof(Node));
novo->val = x;
novo->next = NULL;
if (!L->head)
L->head = novo;
else
L->tail->next = novo;
L->tail = novo;
}
List* INTER(List* L1, List* L2) {
List* L3 = createList();
for (Node* p = L1->head; p; p = p->next) {
if (search(L2, p->val)) {
append(L3, p->val);
}
}
return L3;
}

Exercícios relacionados