Dadas duas listas encadeadas e dinâmicas L1 e L2, implemente a operação UNION, que cria uma terceira lista L3 com a união entre as duas listas.

Passo 1

O exercício pede para implementar a operação UNION sobre duas listas encadeadas dinâmicas L1 e L2, gerando uma terceira lista L3 que contenha todos os valores que aparecem em L1 ou em L2, mas sem repetições. O conteúdo da matéria é estrutura de dados (listas encadeadas) e vamos precisar saber como percorrer listas, inserir nós e fazer busca de um valor na lista.

Passo 2

Começamos criando L3 vazia, isto é, inicializamos o ponteiro cabeça de L3 com NULL.

Passo 3

Percorremos L1 usando um ponteiro auxiliar. Para cada nó de L1 encontramos, copiamos seu valor e inserimos esse valor em L3 no final. Como L3 está vazia ou ainda não tem esse valor, não precisamos de checagem nessa etapa.
Depois, percorremos L2 com outro ponteiro auxiliar. Para cada valor encontrado em L2 fazemos uma busca em L3: se a busca NÃO encontrar esse valor em L3, então inserimos o valor no final de L3. Se já existir, pulamos para o próximo nó de L2.

Passo 4

Ao final desses dois percursos teremos L3 contendo todos os elementos de L1 e de L2, sem duplicatas.

Passo 5

A complexidade desse algoritmo é O(n1·m + n2·m), onde n1 é o tamanho de L1, n2 o tamanho de L2 e m o tamanho de L3 durante as buscas. Se quisermos otimizar, podemos usar uma tabela de hash auxiliar para reduzir buscas a O(1).

Resposta

Pseudocódigo da operação UNION:
function UNION(L1, L2):
L3 ← lista vazia
// Insere todos os elementos de L1 em L3
p ← L1.head
while p ≠ NULL do
    insertTail(L3, p.value)
    p ← p.next
end while

// Insere em L3 apenas os elementos de L2 que ainda não estão em L3
q ← L2.head
while q ≠ NULL do
    if not contains(L3, q.value) then
        insertTail(L3, q.value)
    end if
    q ← q.next
end while

return L3
// Função que checa se um valor está presente na lista
function contains(List, x):
r ← List.head
while r ≠ NULL do
if r.value = x then
return true
end if
r ← r.next
end while
return false
// Função que insere um valor no final da lista
function insertTail(List, x):
novo ← new Node(x)
novo.next ← NULL
if List.head = NULL then
List.head ← novo
else
t ← List.head
while t.next ≠ NULL do
t ← t.next
end while
t.next ← novo
end if

Exercícios relacionados