#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct node{
    int data;
    struct node *next;
    }link,*linkptr;
void creatlink(linkptr &la,int n)
{
    linkptr q1,q2;
    int i;
    for(i=0;i<n;i++)
    {
        q1=(linkptr)malloc(sizeof(link));
        if(!q1)printf("error");
        scanf("%d",&q1->data);
        if(i==0)
        {
            //q1->next=NULL;
            la=q2=q1;
        }
        else
        {
            q2->next=q1;
            q2=q1;
        }

        if(i==n-1)
        q2->next=NULL;
    }


}
void insert(linkptr &la,int x,int i)
{
    linkptr q1,q2,p;
    int k=1;
    q1=q2=la;
    p=(linkptr)malloc(sizeof(link));
    p->data=x;
    if(i==1)
    {
        p->next=la;
        la=p;
    }
    else
    {
           while(k<i-1)
            {
                q2=q1->next;
                q1=q2;
                k++;
            }//找到要插入的上一个节点q1、q2指向它
            q2=q1->next;
            q1->next=p;
            p->next=q2;
            //printf("\n");
    }
}
void delink(linkptr &la,int j)
{
    linkptr q1,q2;
    int k=1;
    q1=q2=la;
    if(j==1)
    {
        la=q1->next;
        free(q1);
        //q1=q2=la;
    }
    else
    {
           while(k<j-1)
            {
                q2=q1->next;
                q1=q2;
                k++;
            }//找到要删除的上一个节点

            q2=q1->next->next;
            free(q1->next);
            q1->next=q2;
            //q1=q2=la;
            //printf("\n");
    }
}
void exchange(linkptr &la,int n)
{
    linkptr q1,q2,p,q;
    p=q=(linkptr)malloc(sizeof(link));
    p->next=la;
    int k=1;
    while(k<n)
    {
        q1=q2=la;
        q2=q1->next;
        while(q2->next!=NULL)
        {
        q1=q2;
        q2=q1->next;
        }//让q2指向最后一个,q1址前一个；
        q1->next=NULL;//
        q2->next=la;
        p->next=q2;//
        p=q2;
        k++;
    }//进行n-1次，
    //实现调换
    la=q->next;
}
void view(linkptr p)
{
    linkptr q1,q2;
    q1=q2=p;
    q2=q1->next;
    while(q2!=NULL)//让q1来遍历链表
    {
        printf("%d ",q1->data);
        q1=q2;
        q2=q1->next;//移动指针
    }
    printf("%d ",q1->data);
    printf("\n");
}
void uninlink(linkptr &la,linkptr lb)
{
    linkptr p,m,n;
    //q1=la;p1=lb;q2=q1->next;p2=p1->next;
    m=n=p=(linkptr)malloc(sizeof(link));
    m->next=NULL;
    while(la!=NULL&&lb!=NULL)//
    {

            if(la->data<lb->data)
            {
                m->next=la;
                n=m->next;
                m=n;
                la=la->next;
            }
            else
            {
                m->next=lb;
                n=m->next;
                m=n;
                lb=lb->next;
            }
    }


  if (la==NULL)
    {
       m->next=lb;
    }
  else
       m->next=la;
    la=p->next;
}
void serch(linkptr la,int y,int n)
{
    linkptr q1,q2;
    int k=1;
    int shu=0;
    q1=q2=la;
    q2=q1->next;
    while(k<n)//让q1来遍历链表
    {
        if(q1->data==y)
        {
           printf("找到，%d在第%d个位置\n",y,k);
           shu=1;
        }
        q1=q2;
        q2=q1->next;//移动指针
        k++;


    }
    if(q1->data==y)
    {
        printf("找到，%d在第%d个位置\n",y,k);
        //k++;
        shu=1;
    }
    if(shu==0)
    {
       printf("没找到\n");
    }

}
int main()
{
    int n,x,i,j,y,m;
    linkptr la,lb;
    //printf("输入线性表La的长度:");
    scanf("%d",&n);
    //printf("输入线性表La中的元素:");
    creatlink(la,n);
    printf("创建好的线性表La=");
    view(la);
    scanf("%d%d",&x,&i);
    insert(la,x,i);
    printf("插入一个元素后的线性表La=");
    view(la);
    //printf("输入要删除元素的位置:");
    scanf("%d",&j);
    delink(la,j);
    printf("删除一个元素后的线性表La=");
    view(la);
    //printf("输入要查找的元素:");
    scanf("%d",&y);
    serch(la,y,n);
    exchange(la,n);
    printf("逆置后的线性表La=");
    view(la);
    //printf("输入线性表Lb的长度:");
    scanf("%d",&m);
    creatlink(lb,m);
    //view(lb);
    uninlink(la,lb);
    printf("合并La和Lb后的线性表=");
    view(la);
    return 0;
}