#include <iostream>
using namespace std;
struct Nod{  int info;  Nod* leg; };
void adaugs(Nod *&prim,Nod *&ultim,int  x)
{   
     Nod*nou=new Nod;
     nou->info=x;
     nou->leg=NULL;
     if(prim==NULL) {prim=nou;ultim=nou;}
     else ultim->leg=nou;
     ultim=nou;}  
void LsiInterclasare(Nod *h1, Nod *h2, Nod *&h)
{
    Nod *p1, *p2, *ult; 
    p1 = h1; p2 = h2;
    if (p1->info <= p2->info)
    {   h = p1; p1 = p1->leg;  }
    else
    {   h = p2;  p2 = p2->leg;  }
    ult = h;
    while (p1 != NULL && p2 != NULL)
      if (p1->info <= p2->info)
      {
        ult->leg = p1;
        p1 = p1->leg;
        ult = ult->leg;  }
      else
      {
        ult->leg = p2;
        p2 = p2->leg;
        ult = ult->leg; }
     if (p1 != NULL) ult->leg = p1;
     else ult->leg = p2;
     //Nod *a=h1,*b=h2;
     //while(a!=NULL) {cout<<a->info<<' ';a=a->leg;} // 1 2 2 3 3 4 4 5
     //cout<<endl;
     //while(b!=NULL) {cout<<b->info<<' ';b=b->leg;} // 2 3 3 4 4 5
     //cout<<endl;
}
int main()
{
    int x,v;
    Nod* prim1=NULL;Nod*  ultim1=NULL; Nod* prim2=NULL; Nod* ultim2=NULL;Nod* P;
    x=1;
    while(x<=4) adaugs(prim1,ultim1,x++); //1 2 3 4
    x=2;
    while(x<=5) adaugs(prim2,ultim2,x++); //2 3 4 5
    LsiInterclasare(prim1,prim2,P);
    Nod *Q=P;
    while(Q!=NULL) {cout<<Q->info<<' ';Q=Q->leg;} //1 2 2 3 3 4 4 5
    cout<<endl;
    Nod *a=prim1,*b=prim2;
    while(a!=NULL) {cout<<a->info<<' ';a=a->leg;} // 1 2 2 3 3 4 4 5
    cout<<endl;
    while(b!=NULL) {cout<<b->info<<' ';b=b->leg;} // 2 3 3 4 4 5
    cout<<endl;
    return 0;
}