Este artigo descreve um algoritmo para mesclar duas listas ligadas simples ordenadas de forma crescente, resultando em uma única lista ordenada sem elementos duplicados, armazenada na primeira lista original.

Problema

Dadas duas listas ligadas A e B, ambas com ordenação crescente, o objetivo é incorporar os nós de B em A, mantendo a propriedade de ordenação e eliminando valores repetidos. O processo ocorre in-place, aproveitando a estrutura existente.

Algoritmo

A solução utiliza dois ponteiros para percorrer as listas de maneira semelhante à fase de merge do mergesort, com tratamento adicional para duplicatas.

Inicialização

Nodo* cursor_a = cabeca_a;
Nodo* cursor_b = cabeca_b->proximo;

O ponteiro cursor_a percorre a lista A a partir do nó cabeçalho, enquanto cursor_b aponta para o primeiro nó válido de B.

Lógica Principal

O loop principal compara o valor de cursor_b com o valor do próximo nó de cursor_a:

• Se cursor_b->valor < cursor_a->proximo->valor, insere o nó de B entre cursor_a e cursor_a->proximo.
• Se os valores forem iguais, ignora o nó de B para evitar duplicatas.
• Se cursor_b->valor > cursor_a->proximo->valor, avança o ponteiro cursor_a.

Caso ocorra duplicata durante a inserção, o nó de B é descartado antes de prosseguir.

Tratamento de Nós Restantes

Quando cursor_a->proximo se torna nulo, a lista A foi totalmente percorrida. Os nós remanescentes de B são adicionados ao final de A, com verificação de duplicatas contra o último valor de A.

Implementação em C++

Abaixo segue o código completo com funções para criar listas, realizar a fusão e exibir o resultado. Os nomes de variáveis e funções foram alterados para refletir uma estrutura alternativa.

#include <iostream>
#include <vector>
using namespace std;

struct Nodo {
    int valor;
    Nodo* proximo;
};

void construir_lista(Nodo* cabeca, const vector<int>& elementos) {
    Nodo* ponteiro_final = cabeca;
    for (int num : elementos) {
        Nodo* novo = new Nodo{num, nullptr};
        ponteiro_final->proximo = novo;
        ponteiro_final = novo;
    }
}

void fundir_listas_ordenadas(Nodo* cabeca_a, Nodo* cabeca_b) {
    Nodo* ptr_a = cabeca_a;
    Nodo* ptr_b = cabeca_b->proximo;

    while (ptr_a->proximo && ptr_b) {
        if (ptr_b->valor < ptr_a->proximo->valor) {
            if (ptr_b->valor == ptr_a->valor) {
                ptr_b = ptr_b->proximo;
                continue;
            }
            Nodo* no_temp = ptr_b;
            ptr_b = ptr_b->proximo;
            no_temp->proximo = ptr_a->proximo;
            ptr_a->proximo = no_temp;
            ptr_a = ptr_a->proximo;
        } else if (ptr_b->valor == ptr_a->proximo->valor) {
            ptr_b = ptr_b->proximo;
        } else {
            ptr_a = ptr_a->proximo;
        }
    }

    while (ptr_b) {
        if (ptr_b->valor != ptr_a->valor) {
            Nodo* no_temp = ptr_b;
            ptr_b = ptr_b->proximo;
            no_temp->proximo = nullptr;
            ptr_a->proximo = no_temp;
            ptr_a = ptr_a->proximo;
        } else {
            ptr_b = ptr_b->proximo;
        }
    }
}

void exibir_lista(Nodo* cabeca) {
    Nodo* atual = cabeca->proximo;
    while (atual) {
        cout << atual->valor << " ";
        atual = atual->proximo;
    }
    cout << endl;
}

int main() {
    int n1, n2;
    cout << "Quantidade de elementos na lista A: ";
    cin >> n1;
    cout << "Quantidade de elementos na lista B: ";
    cin >> n2;

    vector<int> dados_a(n1), dados_b(n2);
    cout << "Insira os elementos de A: ";
    for (int i = 0; i < n1; i++) cin >> dados_a[i];
    cout << "Insira os elementos de B: ";
    for (int i = 0; i < n2; i++) cin >> dados_b[i];

    Nodo* cabeca_a = new Nodo{0, nullptr};
    Nodo* cabeca_b = new Nodo{0, nullptr};

    construir_lista(cabeca_a, dados_a);
    construir_lista(cabeca_b, dados_b);

    fundir_listas_ordenadas(cabeca_a, cabeca_b);
    exibir_lista(cabeca_a);

    // Nota: a liberação de memória foi omitida por simplicidade
    return 0;
}