#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct Nod
{
    int info;
    Nod *leg;
};

struct Lista                            /// Simplu inlantuita
{
    Nod *L;
    void Inserare1(int x)               /// Inserare la inceput
    {
        Nod *p;
        p = new Nod;
        p -> info = x;
        p -> leg = L;
        L = p;
    }

    void Inserare2(Nod *p, int x)       /// Inserare dupa nodul de adresa memorata in p
    {
        Nod *q;
        q = new Nod;
        q -> info = x;
        q -> leg = p -> leg;
        p -> leg = q;
    }

    ///     Insereaza dupa al k-lea nod
    /// un nou nod cu informatia x;
    /// Daca lista are mai putin de
    /// k noduri, inserarea se face
    /// la sfarsitul listei.
    void Inserare3(int k, int x)
    {
        Nod *p, *q;
        for(p = L; (k > 1) && (p != NULL); p = p -> leg)
        {
            k--;
            q = p;
        }
        if(p == NULL) /// Inserez dupa q
            Inserare2(q, x);
        else /// Inserez dupa p
            Inserare2(p, x);
    }

    void Parcurgere()                   /// Parcurgerea listei
    {
        for(Nod *p = L; p != NULL; p = p -> leg)
            cout << p -> info << " ";
        cout << "\n";
    }

    void Init()                         /// Initializarea listei vide
    {
        L = NULL;
    }

    void Sterge1()                      /// Stergerea primului nod
    {
        if(L = NULL) return;
        Nod *p;
        p = L;
        L = p -> leg;
        delete p;
    }

    void Sterge2(Nod *p)                /// Stergerea nodului dupa nodul de adresa memorata p
    {
        Nod *q;
        q = p -> leg;
        p -> leg = q -> leg;
        delete q;
    }

    Nod *Cautare(int x)                 /// Cautarea valorii x in lista si returnarea pointer-ului
    {
        Nod *p;
        for(p = L; p != NULL; p = p -> leg)
            if(p -> info == x)
                return p;
        return NULL;
    }

    void ParcDS(Nod *p) /// Parcurgerea de la dreapta la stanga a nodurilor listei
    {
        if(p != NULL)
        {
            ParcDS(p -> leg);
            cout << p -> info << " ";
        }
    }
};



int main()
{
    int i, n, x;
    srand(time(0));

    Lista L1; L1.Init();
    n = rand() % 10 + 1;
    x = rand() % 10 + 1;
    L1.Inserare1(x);
    for(i = 2; i <= n; i++)
    {
        x += rand() % 10 + 1;
        L1.Inserare3(i, x);
    }

    Lista L2; L2.Init();
    n = rand() % 10 + 1;
    x = rand() % 10 + 1;
    L2.Inserare1(x);
    for(i = 2; i <= n; i++)
    {
        x += rand() % 10 + 1;
        L2.Inserare3(i, x);
    }

    cout << "L1: "; L1.Parcurgere();
    cout << "L2: "; L2.Parcurgere();

    Lista L; L.Init();
    Nod *p, *q;
    p = L1.L; q = L2.L;
    if(p -> info < q -> info)
    {
        L.Inserare1(p -> info);
        p = p -> leg;
    }
    else
    {
        L.Inserare1(q -> info);
        q = q -> leg;
    }
    int poz = 1;
    while((p != NULL) && (q != NULL))
    {
        if(p -> info < q -> info)
        {
            L.Inserare3(poz++, p -> info);
            p = p -> leg;
        }
        else
        {
            L.Inserare3(poz++, q -> info);
            q = q -> leg;
        }
    }
    while(p != NULL)
    {
        L.Inserare3(poz++, p -> info);
        p = p -> leg;
    }
    while(q != NULL)
    {
        L.Inserare3(poz++, q -> info);
        q = q -> leg;
    }
    cout << "L: "; L.Parcurgere();

    return 0;
}