Listas enlazadas - merge, C++ (gcc)

Language: Layout:

/* 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;
        if (aux->siguiente != nullptr)
            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 llama a una función que inserta ese nodo en la lista. Retorna el puntero inicial. */
Nodo* generar_nodo(Nodo* inicio, int dato) {
    Nodo* nuevo;
    nuevo = new Nodo;
    nuevo->dato = dato;
    nuevo->siguiente = nullptr;
    inicio = insertar_ordenado(inicio, nuevo);
    return inicio;
}

/* 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 (C). */
void recorrer_lista_restante(Nodo* & lista_original, Nodo* & C)
{
    Nodo* anterior;
    while (lista_original != nullptr)
    {
        anterior = lista_original;
        lista_original = lista_original->siguiente;
        anterior->siguiente = nullptr;
        C = insertar_final(C, 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;
    Nodo* anterior;

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

//Continuamos con la lista que no terminó de recorrerse. Para A o B vacías, esta función no hace modificaciones.
    recorrer_lista_restante(A, C);
    recorrer_lista_restante(B, C);
    
    return C;
}

/* Función principal del programa. Se inicializan punteros iniciales de dos listas y se llama
a funciones para cargarlas y luego unificarlas en una sola lista. Se imprimen todas las listas. */
int main(){
    Nodo* A = nullptr;
    A = generar_nodo(A, 5);
    A = generar_nodo(A, 7);
    A = generar_nodo(A, 2);
    A = generar_nodo(A, 5);
    A = generar_nodo(A, 10); 
    
    Nodo* B = nullptr;
    B = generar_nodo(B, 1);
    B = generar_nodo(B, 9);
    B = generar_nodo(B, 8);
    B = generar_nodo(B, 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);    
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.43 sec, absolute running time: 0.08 sec, cpu time: 0.01 sec, memory peak: 3 Mb, absolute service time: 0,51 sec