2013年数据结构第四题（C/C++)

题目如下：

代码实现：

#include
using namespace std;

#define ElemType int
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*linkList; //单链表存储结构

bool InitlinkList(linkList &L)//完成单链表的初始化
{
  L=new LNode;
  L->next=NULL;
  return true;
}

void CreateList_R(linkList &L)//尾插法构造单链表
{
  LNode *p,*r;
  int n;
  r=L;
  cout<<"输入创建单链表的长度:"<>n;
  
  for(int i=0;i>p->data;
     p->next=NULL;
     r->next=p;
     r=p;
  }
  return;
}

void Reverse(linkList &L)//逆置链表
{
 LNode *p=L,*q=L->next,*r=L->next;
 int n=0;
 while(r->next){
    n++;
    r=r->next;
 }
 n++;
 if(n==1)return;
 for(int i=0;inext=q->next;
   q->next=NULL;
   r->next=q;
   r=q;
   q=p->next;
 }
 return; 
}

linkList Combine_and_Change(linkList &L1,linkList &L2)//本题解答
{
 LNode *p1=L1->next,*r1=L1,*p2=L2->next,*r2=L2;
 while(p1&&p2)
 {
  if(p1->datadata)
  {
    r1->next=p1->next;
    free(p1);
    p1=r1->next;
  }
  else if(p2->datadata)
  {
    r2->next=p2->next;
    free(p2);
    p2=r2->next;
  }
  else{
    p1=p1->next;r1=r1->next;
    p2=p2->next;r2=r2->next;
  }
 }
 if(p1&&!p2)
 {
   while(p1){
     r1->next=p1->next;
     free(p1);
     p1=r1->next;
   }
 }
 if(L1->next)Reverse(L1);//将递增的链表变为递减的
 return L1;
}

void ShowList(linkList &L)
{
  if(L->next==NULL){
    cout<<"此链表为空"<next;
  while(p)
  {
    cout<data<<" ";
    p=p->next;
  }
  cout<next;
   while(q)
   {
     delete p;
     p=q;
     q=q->next;
   }
   delete p;
   return;
}

int main()
{
   linkList A,B;
   InitlinkList(A);//初始化单链表A
   InitlinkList(B);//初始化单链表B

   cout<<"创建单链表A:"<