Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Samosa
The Menu
Calc
Good pairs
a
ExceptionWhat
Hello World
Finding the first digit of a number
queue
Zahra_matrix