原文题是严蔚敏同志的数据结构习题中第二章线性表中提出的问题。
原问如下：
2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表与B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元表)排列的线性表C，并要求利用原表(即A表与B表)的结点空间构造C表。
分析：对两个或两个以上，结点按元素值递增/减排列的单链表进行操作时，应采用"指针平行移动、一次扫描完成"的策略。且链表A与链表B的长度大小不一定相等。
代码：
#include<iostream>
using namespace std;
typedef int ElemType;
//两个递增的链表合并成递增的链表。
typedef struct LNode
{
ElemType data;
struct LNode *next;
}
LNode;
typedef LNode *LinkList;
void CreatList(LinkList &L,int n)
{
LinkList p,q;
L=new LNode;
L->next=NULL;
q=L;
cout<<"请从小到大输入链表的元素：";
for (int i=1;i<=n;i++)
{
p=new LNode;
cin>>p->data;
p->next=q->next;
q->next=p;
q=q->next;
}
cout<<"所创建得的递增有序链表为：";
p=L->next;
for (int j=1;j<=n;j++)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void CreatC(LinkList &A,LinkList &B,LinkList &C,int n)
{
LinkList pa,pb,pc,pre=NULL/**//*C结点的上一个结点*/,q/**//*t*/;
pa=A->next;
pb=B->next;
// C=t=A;// A
while (pa||pb)
{
if (!pb||((pa&&pb)&&(pa->data<pb->data)))
{
/**/////将A的元素插入新表
pc=pa;
q=pa->next;
pa->next=pre;
pa=q;
}
else
{
pc=pb;
q=pb->next;
pb->next=pre;
pb=q; //将B的元素插入新表
}
pre=pc;
}
cout<<"合并后的递减有序链表为：";
C=A;
A->next=pc;
pa=pc;
for (int j=1;j<=n;j++)
{
cout<<pa->data<<" ";
pa=pa->next;
}
cout<<endl;
getchar();
}
void main()
{
LinkList A,B,C;
int n,m,k;
cout<<"请输入链表***A***的长度：";
cin>>n;
CreatList(A,n);
cout<<"请输入链表***B***的长度：";
cin>>m;
CreatList(B,m);
k=m+n;
CreatC(A,B,C,k);
system(0);
getchar();
}