#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int

typedef int Status;
typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*LinkList;


int CreateLink_L(LinkList &L,int n)
{
// 创建含有n个元素的单链表
  LinkList p,q;
  int i;
  L=(LinkList)malloc(sizeof(LNode));
  L->next=NULL;              // 先建立一个带头结点的单链表
  q=(LinkList)malloc(sizeof(LNode));
  q=L;
  for(i=0;i<n;i++)
  {
    p=(LinkList)malloc(sizeof(LNode));  // 生成新结点
    q->next=p;
    q=p;
  }
  p->next=NULL;
  return OK;
}
int CreateLink_C(LinkList &L,int n)
{
// 创建含有n个元素的单链表
  LinkList p,q;
  int i;
  L=(LinkList)malloc(sizeof(LNode));
  L->next=NULL;              // 先建立一个带头结点的单链表
  q=(LinkList)malloc(sizeof(LNode));
  q=L;
  for(i=0;i<n;i++)
  {
    p=(LinkList)malloc(sizeof(LNode));  // 生成新结点
    q->next=p;
    q=p;
  }
  p->next=NULL;
  return OK;
}

int LoadLink_L(LinkList &L)
{
// 单链表遍历
 LinkList p=L->next;
 if(!L->next)
     printf("The List is empty!");
 else
 {
     while(p)
     {
        printf("%d ",p->data);
        p=p->next;
     }
 }
 printf("\n");
 return OK;
}


Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
  // 在带头结点的单链线性表L的第i个元素之前插入元素e
  LinkList p,s;
  p = L;   
  int j = 0;
  while (p && j < i-1) {  // 寻找第i-1个结点
    p = p->next;
    ++j;
  }
  if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
  s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
  s->data = e;  s->next = p->next;      // 插入L中
  p->next = s;
  return OK;
} // LinstInsert_L

Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
  // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
  LinkList p,q;
  p = L;
  int j = 0;
  while (p->next && j < i-1) {  // 寻找第i个结点，并令p指向其前趋
    p = p->next;
    ++j;
  }
  if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
  q = p->next;
  p->next = q->next;           // 删除并释放结点
  e = q->data;
  free(q);
  return OK;
} // ListDelete_L

void MergeList_L(LinkList La,LinkList Lb,LinkList &Lc)
{
   LinkList pa,pb,pc;
   pa=La->next;
   pb=Lb->next;
   Lc=pc=La;
   while(pa&&pb)
   {
       if(pa->data<=pb->data)
       {
           pc->next=pa;
           pc=pa;
           pa=pa->next;
       }
       else
       {
           pc->next=pb;
           pc=pb;
           pb=pb->next;
       }
   }
   pc->next=pa?pa:pb;
}
void input_L(LinkList &L,int n)//输入链表数据
{
    int i;
    LinkList p;
    ElemType e;
    p=L->next;
    for(i=0;i<n;i++)
    {
        scanf("%d",&e);
        p->data=e;
        p=p->next;
    }
}
void main()
{
    LinkList A,B,C;
    int n,k;
    scanf("%d",&n);
    CreateLink_L(A,n);
    input_L(A,n);
    scanf("%d",&k);
    CreateLink_L(B,k);
    input_L(B,k);
    CreateLink_L(C,n+k);
    MergeList_L(A,B,C);
    printf("List A:");
    LoadLink_L(A);
    printf("List B:");
    LoadLink_L(B);
    printf("List C:");
    LoadLink_L(C);
}