#include<iostream>
#include<conio.h>
using namespace std;

struct Nod

      {int info;
       Nod *next,*back;
       };

Nod *prim, *ultim;

void mutaup()
 {Nod *u=prim;
  while(u->next) u=u->next;
  u->back->next=0;
  u->back=0;
  u->next=prim;
  prim->back=u;
  prim=u;
 }

 void inter()
 {Nod *p=prim,*r,*q,*s;
  while(p->next)
   {q=p->next;
    r=p->back;
    s=q->next;
    if(r) r->next=q;
   q->back=r;
   p->next=s;
   if(s) s->back=p;
  p->back=q;
  q->next=p;
  if(p==prim) prim=q;
  p=p->next;
 }
}

void creare_lista()

{Nod *c;
 c=new Nod;
 cout<<"info ";
 cin>>c->info;
 if(!prim)
   {prim=c;
    prim->next=0;
    prim->back=0;
    ultim=prim;
    }
 else
   {ultim->next=c;
    c->back=ultim;
    ultim=c;
    ultim->next=0;
   }
}

void listare_stanga_dreapta()
{Nod *c;
 c=prim;
 while(c)
    {cout<<c->info<<" ";
     c=c->next;}
}

void listare_dreapta_stanga()
{Nod *c;
 c=ultim;
 while(c)
    {cout<<c->info<<" ";
     c=c->back;}
}

int main()
   {int n,i;
    //clrscr();
    cout<<"cate elemente va avea lista?";
    cin>>n;
    for(i=1;i<=n;i++)
      creare_lista();
    cout<<endl<<"Elementele listei de la stanga la dreapta sunt:"<<endl;
    listare_stanga_dreapta();
    cout<<endl<<"Elementele listei de la dreapta la stanga sunt:"<<endl;
    listare_dreapta_stanga();

    //mutaup();
    //cout<<endl<<"Elementele listei de la stanga la dreapta "<<endl<< "dupa ce a primit ca parametru adresa primului nod al listei"<<endl<<" si a mutat ultimul nod in fata primului sunt:"<<endl;
    //cout<<"test"<<endl;
    inter();
    // !!!INtrodu n impar
    cout<<endl<<"Elementele listei de la stanga la dreapta"<<endl<<" dupa ce primeste ca parametru adresa primului nod al listei"<<endl<<"  si interschimba primul nod cu cel de-al doilea,"<<endl<<"  al treilea cu cel de-al patrulea si asa mai departe sunt:"<<endl;
    listare_stanga_dreapta();

    //cout<<endl<<"Elementele listei de la dreapta la stanga sunt:"<<endl;
    //listare_dreapta_stanga();
    getch();
    return 0;
    }