/*
Dadas dos listas LISTA y LISTB (nodo = registro + puntero), desarrollar y codificar un
procedimiento que genere otra lista LISTC por apareo del campo LEGAJO del registro
(define orden creciente en ambas). Nota: LISTA y LISTB dejan de ser útiles después del
apareo).
 */

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct Nodo{
    int info;
    Nodo* sgte;
};

Nodo* InsertarPrimero(Nodo* &lista, int valor){
    Nodo *p = new Nodo();
    p->info = valor;
    p->sgte = lista;
    lista = p;
    return p;
}

Nodo* InsertarEnMedio(Nodo* &lista, int valor){
    Nodo* q = new Nodo();
    Nodo* p = lista;
    q->info = valor;
    while (p->sgte != NULL && valor > p->sgte->info){
        p = p->sgte;
    }
    q->sgte = p->sgte;
    p->sgte = q;
    return q;
}

Nodo* InsertarOrdenado(Nodo* &lista, int valor){
    Nodo* nuevo = NULL;
    if (lista == NULL || valor < lista->info) {
        nuevo = InsertarPrimero(lista, valor);
    } else{
        nuevo = InsertarEnMedio(lista, valor);
    }
    return nuevo;
}

void LlenarListasOrdenado(Nodo* &lista, int desde, int hasta, int incremento){

    for (int i = desde; i < hasta; i+= incremento) {
        InsertarOrdenado(lista, i);
    }
}

Nodo* AparearListas(Nodo* &listaA, Nodo* &listaB){

    Nodo* A = listaA;
    Nodo* B = listaB;
    Nodo* listaAB = NULL;

    while(A != NULL && B != NULL){
        if(A->info < B->info){
            InsertarOrdenado(listaAB, A->info);
            A = A->sgte;
        }else{
            InsertarOrdenado(listaAB, B->info);
            B = B->sgte;
        }
    }

    while(A != NULL){
        InsertarOrdenado(listaAB, A->info);
        A = A->sgte;
    }

    while(B != NULL){
        InsertarOrdenado(listaAB, B->info);
        B = B->sgte;
    }


    return listaAB;

}

void MostrarLista(Nodo* &lista){
    Nodo* p = lista;
    while (p != NULL){
        cout << p->info << endl;
        p = p->sgte;
    }
}

int main() {
    //Inicializo variables
    Nodo* listaA = NULL;
    Nodo* listaB = NULL;
    Nodo* listaAB = NULL;
    srand( time(NULL) );

    //Lleno las listas con valores en orden
    LlenarListasOrdenado(listaA,0,10,2);
    LlenarListasOrdenado(listaB,1,10,2);

    //Apareo las listas
    listaAB = AparearListas(listaA, listaB);

    //Muestro la lista final
    MostrarLista(listaAB);

    return 0;
}