final 1a - interseccion

/* 1. Intersección
Temas evaluados: Listas enlazadas, abstracción procedural, estructuras de control, y lenguaje de programación.
1a. Escriba en Pascal, (puede ser C o C++, si asi lo decidiera) el encabezado de una función o procedimiento que reciba
dos listas enlazadas de enteros, a y b, y genere una tercera, c, con la intersección de a y b. Asuma que las listas a y b están
ordenadas y que no contienen repeticiones. La lista c debe generse ordenada. Escriba la definición de los tipos de datos no
primtivos utilizados. Utilice el pasaje por referencia correctamente.
*/

#include <iostream>
using namespace std;

struct node {
  int entry = 0; // valores por defecto
  node *next = nullptr;
};
struct lista {
    node* root = nullptr;
};

void mostrar_lista (lista& l);
bool is_vacia (lista &l);
void mostrar_vacia (lista& l);
int get_by_index (lista& l, int index);
void insertar_nodo_al_final (lista &l, int a);
void insertar_nodo_en_index(lista& l, int index, int valor);
void eliminar_nodo_en_index (lista& l, int index);
void eliminar_lista (lista& l);
int buscar_elemento (lista& l, int e);

void interseccion (const lista& a, const lista& b, lista& c)
{
    node* p = a.root;
    node* q = b.root;

    while (p != 0 and q != 0)
    {
        if (p->entry == q->entry)
        {
            insertar_nodo_al_final(c,p->entry);
            p = p->next;
            q = q->next;
            continue;
        }

        if (p->entry < q->entry)
            p = p->next;
        else
            q = q->next;
    }
}

int main()
{
    lista L, M, I;

    for (int i=0; i<5; i++)
        insertar_nodo_al_final (L, i+1);
    for (int i=0; i<5; i++)
        insertar_nodo_al_final(M, i+3);

//  insertar_nodo_al_final(I, 0);

    interseccion(L,M,I);

    mostrar_lista(L);
    mostrar_lista(M);

    if (is_vacia(I))
        cout << "lista vacia" << endl;
    else
        mostrar_lista(I);

    return 0;
}

void mostrar_lista (lista& l) // funciona
{
    for (node *p = l.root; p != 0; p = p->next)
        cout << p->entry << ' ';
    cout << endl;
}

bool is_vacia (lista &l) // funciona
{
    return l.root == 0;
}

void mostrar_vacia (lista& l) // funciona
{
    if (is_vacia(l))
        cout << "esta vacia" << endl;
    else
        cout << "no esta vacia" << endl;
}

int get_by_index (lista& l, int index) // funciona
{
    node* p = l.root;
    for (int i=0; i < index; i++)
    {
        p = p->next;
    }
    return p->entry;
}

void insertar_nodo_al_final (lista &l, int a) // funciona
{
    node* nuevo = new node;
    nuevo->entry = a;
    if (l.root != 0) // apunta a algo?
    {
        node* p = l.root;
        while (p->next != 0)
            p = p->next;
        p->next = nuevo;
    }
    else
        l.root = nuevo;
}

void insertar_nodo_en_index(lista& l, int index, int valor) // funciona
{
    node* nuevo = new node;
    nuevo->entry = valor;

    if (index != 0)
    {
        node* p = l.root;
        for (int i = 0; i < index - 1; i++)
        {
            p = p->next;
        }
        nuevo->next = p->next;
        p->next = nuevo;
    }
    else
    {
        nuevo->next = l.root;
        l.root = nuevo;
    }
}

void eliminar_nodo_en_index (lista& l, int index) // funciona
{
    node* p = l.root;
    if (index != 0)
    {
        node* q = l.root;
        for (int i = 0; i < index - 1; i++)
        {
            p = p->next;
        }
        q = p->next->next;
        delete p->next;
        p->next = q;
    }
    else
    {
        l.root = p->next;
        delete p;
    }
}

void eliminar_lista (lista& l) // funciona
{
    while (l.root != 0)
        eliminar_nodo_en_index(l,0);
}

int buscar_elemento (lista& l, int e) // funciona
{
    int index = 0;
    node* p = l.root;
    while (p->entry != e and p->next != 0) // p->next == 0  => es el ultimo
    {
        p = p->next;
        index++;
    }

    if (p->entry == e)
        return index;
    else
        return -1;
}