Listas enlazadas - merge, C++ (gcc)

Listas enlazadas - merge

/* Implementar una función que reciba dos listas ordenadas de números enteros y las combine generando
una tercera lista, también ordenada, reutilizando los nodos. */

#include <iostream>
using namespace std;

struct Nodo {
    int dato;
    Nodo * siguiente;
};

/* Dado el puntero inicial a una lista y el puntero a un nuevo nodo que aún no
está en la lista, inserta este nuevo nodo al final. Retorna el puntero inicial. */
Nodo* insertar_final(Nodo*  inicio, Nodo* nuevo)
{
    if (inicio == nullptr)
        inicio = nuevo;
    else {
        Nodo* aux = inicio;
        while (aux->siguiente != nullptr)
            aux = aux->siguiente;
        aux->siguiente = nuevo;
    }
    return inicio;
}

/* Dado el puntero inicial a una lista y el puntero a un nuevo nodo que aún no
está en la lista, inserta este nuevo nodo en orden ascendente. Retorna el puntero inicial. */
Nodo* insertar_ordenado(Nodo* inicio, Nodo* nuevo)
{
    if (inicio == nullptr || nuevo->dato < inicio->dato)
    {
        nuevo->siguiente = inicio;
        inicio = nuevo;
    }
    else
    {
        Nodo* aux = inicio;
        while (aux->siguiente != nullptr && aux->siguiente->dato < nuevo->dato)
        {
            aux = aux->siguiente;
        }
        nuevo->siguiente = aux->siguiente;
        aux->siguiente = nuevo;
    }
    return inicio;
}

/* Genera un nuevo nodo con el dato pasado por parámetro y el puntero al siguiente en nullptr,
y retorna un puntero al nuevo nodo. */
Nodo* generar_nodo(int dato) {
    Nodo* nuevo = new Nodo;
    nuevo->dato = dato;
    nuevo->siguiente = nullptr;
    return nuevo;
}

/* Imprime en pantalla todos los elementos de la lista. */
void imprimir(Nodo* inicio){
    for (Nodo* aux = inicio; aux != nullptr; aux = aux->siguiente)
        cout << aux->dato << endl;
}

/* Recorre la lista original correspondiente al primer puntero pasado por parámetro,
(lista_original) reubicando cada nodo en la lista apuntada por el segundo parámetro (lista_nueva). */
void reinsertarNodo(Nodo* & lista_original, Nodo* & lista_nueva)
{   
    Nodo* anterior = lista_original;
    lista_original = lista_original->siguiente;
    anterior->siguiente = nullptr;
    lista_nueva = insertar_final(lista_nueva, anterior);
}

/* Unifica dos listas pasadas por parámetro, las cuales quedan luego vacías.
Retorna el puntero inicial de la lista unificada. */
Nodo * merge(Nodo * & A, Nodo * & B) {
    Nodo* C = nullptr;   //puntero a la lista unificada

//Recorre mientras haya nodos en ambas listas
    while (A != nullptr && B != nullptr) {
        if (A->dato <= B->dato){
            reinsertarNodo(A, C);
        }
        else {
            reinsertarNodo(B, C);
        }
    }

//Continuamos con la lista que no terminó de recorrerse.
    while (A != nullptr) {
        reinsertarNodo(A, C);
    }
    while (B != nullptr) {
        reinsertarNodo(B, C);
    }
    
    return C;
}

/* Función principal del programa. Se inicializan punteros iniciales de dos listas y se llama
a funciones para cargarlas. Luego se las unifica en una sola lista. Se imprimen todas las listas. */
int main(){
    Nodo* A = nullptr;
    A = insertar_ordenado(A, generar_nodo(5));
    A = insertar_ordenado(A, generar_nodo(7));
    A = insertar_ordenado(A, generar_nodo(2));
    A = insertar_ordenado(A, generar_nodo(5));
    A = insertar_ordenado(A, generar_nodo(10));

Nodo* B = nullptr;
    B = insertar_ordenado(B, generar_nodo(7));
    B = insertar_ordenado(B, generar_nodo(9));
    B = insertar_ordenado(B, generar_nodo(8));
    B = insertar_ordenado(B, generar_nodo(4));
   
    cout << "LISTA A:" << endl;
    imprimir(A);
    cout << endl;
    cout << "LISTA B:" << endl;
    imprimir(B);
    
    cout << endl;
    cout << "LISTA UNIFICADA:" << endl;
    Nodo* C = merge(A, B);
    imprimir(C);    
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development