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

题目：

我的代码实现：

#include
using namespace std;

#define ElemType int
typedef struct LNode
{
 ElemType data;
 struct LNode* next;
}LNode,*linkList;

void CreateList_R(linkList &L)//尾插法创建单链表
{
 LNode *p,*r;
 int n;
 L=new LNode;
 L->next=NULL;
 r=L;
 cin>>n;
 while(n!=9999)
 {
  p=new LNode;
  p->data=n;
  p->next=NULL;
  r->next=p;
  r=p;
  cin>>n;
 }
}

linkList Combine_and_Upside(linkList &A,linkList &B)//本题解答
{
 LNode *p1,*p2,*q1,*q2;
 linkList C;
 C=new LNode;
 C->next=NULL;
 p1=A,p2=B,q1=A->next,q2=B->next;
 
 while(p1->next&&p2->next)
 {
  if(q1->data>q2->data)
  {
   p1->next=q1->next;
   q1->next=C->next;
   C->next=q1;
   q1=p1->next;
  }
  else if(q2->data>=q1->data)
  {
   if(q2->data==q1->data)
   {
    p1->next=q1->next;
    delete q1;
    q1=p1->next;
   }
   p2->next=q2->next;
   q2->next=C->next;
   C->next=q2;
   q2=p2->next;
  }
 }
 while(p1->next)
 {
  q1=p1->next;
  p1->next=q1->next;
  q1->next=C->next;
  C->next=q1;
  q1=p1->next;
 }
 while(p2->next)
 {
  q2=p2->next;
  p2->next=q2->next;
  q2->next=C->next;
  C->next=q2;
  q2=p2->next;
 }
 delete A;
 delete B;
 return C;
}

void ShowList(linkList &L)//显示自己的操作结果
{
  LNode *k=L->next;
  printf("打印整个操作后的单链表的情况:n");
  while(k){
   printf(" %d ",k->data);
   k=k->next;
  }
  printf("n");
}

void DestroyList(linkList &L)//销毁单链表
{
 LNode *P=L;
 while(L)
 {
  L=L->next;
  printf("n成功删除%dn",P->data);
  delete P;
  P=L;
 }
}

int main()
{
  linkList A,B; //定义两个递减有序的单链表
  linkList C;
  printf("n创建递减有序单链表A:n");
  CreateList_R(A);
  printf("n创建递减有序单链表B:n");
  CreateList_R(B);

  C=Combine_and_Upside(A,B);//本题解答：将A、B合并成一个递增有序的单链表
  
  ShowList(C);//展示新的单链表
  DestroyList(C);//销毁单链表
}

算法思想：在两个链表的头部各放置指针，然后同时开始向前移动并不断比较所指向结点中数据的大小。发现较大的数据就将其所在原结点从链表中取出并利用“头插法”将其放在新的头结点的后面。这样不断下去直到两个链表中至少有一个被删除完毕，再将剩下的链表的剩余数据的原结点倒插入新的头结点的后面。