#include <iostream>

using namespace std;

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

int n;

void parcurgere(nod* v)
{
    nod* c=v;
    while(c)
    {
        cout << c->info<<" ";
        n++;
        c=c->leg;
    }
}

nod* creare()
{
    nod* prim, *ultim, *p;
    int nr;
    prim=new nod;
    ultim=prim;
    cout<<"Introduceti un numar: ";
    cin>>nr;
    if (nr==0)
    {
        cout<<"Lista este vida.";
        return 0;
    }
    else
    {
        prim->info=nr;
        prim->leg=NULL;
        cout<<"Introduceti un numar: ";
        cin>>nr;
        while(nr)
        {
            p=new nod;
            p->info=nr;
            ultim->leg=p;
            ultim=p;
            ultim->leg=NULL;
            cout<<"Introduceti un numar: ";
            cin>>nr;
        };
        return prim;
    }
}

int inserare (nod *prim, int k, int inf)
{
    if (k > n + 1)
        return 0;
    else
    {
        nod * p = new nod, *q;
        p -> info = inf;
        if( k == 1)
        {
            p -> leg = prim;
            prim = p;
        }
        else if (k == n + 1)
        {
            q = prim;
            while ( q -> leg)
                q = q -> leg;
            q -> leg = p;
            p -> leg = NULL;
        }
        else
        {
            q = prim;
            int ct = 1;
            while ( ct < k - 1)
            {
                q = q -> leg;
                ct++;
            }
            p -> leg = q -> leg;
            q -> leg = p;
        }
        return 1;
    }
}

int stergere(nod* &prim, int k)
{
    nod *q, *p;
    if(k > n)
        return 0;
    else
    {
        if(k == 1)
        {
            q = prim;
            prim = prim -> leg;
            delete q;
        }
        else if( k == n)
        {
            q = prim;
            while(q -> leg -> leg)
                q = q -> leg;
            p = q;
            p -> leg = NULL;
            delete q -> leg;
        }
        else
        {
            q = prim;
            int ct = 1;
            while(ct < k - 1)
            {
                q = q -> leg;
                ct++;
            }
            p = q -> leg;
            q -> leg = q -> leg -> leg;
            delete p;
        }
    }
    return 1;
}

int main()
{
    nod* prim;
    int k, inf;
    prim=creare();
    parcurgere(prim);
    cout<<" numarul de noduri este "<< n << endl;
    cout << "Introduceti pozitia si valoarea pentru inserare: ";
    cin >> k >> inf;
    if (inserare(prim, k, inf))
        parcurgere(prim);
    else
        cout << "Inserarea nu se afla in lista.";
    cout << "\nDe pe ce pozitie stergeti? ";
    cin >> k;
    stergere(prim, k);
    parcurgere(prim);
    if(stergere(prim, k) == 0)
        cout << "Pozitia introdusa nu se afla in lista"<< endl;
    else
        parcurgere(prim);
    return 0;
}