数据结构与算法----1.10 两递增表归并为一个递减表，利用原表结点的内存空间

[c++]代码库

//***********************************
//功能：把两个递增有序的单链表归并为一个递减的单链表，利用原表结点的内存空间
//日期：2017年9月27日
//作者：Ryan2019
//***********************************
#include <iostream>
using namespace std;
typedef int LElemType;
typedef struct LNode
{
    LElemType data;
	LNode *next;
}* LList;
void ListCreate(LList &L,int n,LElemType a[]);//创建链表
void Listshow(LList &L);//显示链表
bool ListMerge(LList &A,LList &B);//归并

int main()
{
	LList A,B; int m=4,n=6;
	LElemType a[4]={1,2,2,3};
	LElemType b[6]={2,3,4,5,6,7};
	ListCreate(A,m,a);	
	ListCreate(B,n,b);
	cout<<"原链表A为：";	Listshow(A);
	cout<<"原链表B为：";	Listshow(B);
	ListMerge(A,B);
	cout<<"归并后链表为：";	Listshow(A);
	return 0;
}

void ListCreate(LList &L,int n,LElemType a[])
{
	LList p;	int i;
	L=new LNode; L->next=NULL;
	for(i=n-1;i>=0;i--)
	{
		p=new LNode;
		p->data=a[i];
		p->next=L->next;
		L->next=p;
	}
}
void Listshow(LList &L)
{
	LList p;
	for(p=L->next;p;p=p->next)
	{
		cout<<p->data<<" ";
	}
	cout<<endl;
}
bool ListMerge(LList &A,LList &B)
{
	LList p,q,t;
	p=A->next;
	q=B->next;
	A->next=NULL;
	delete B;
	while(p&&q)
	{
		if(p->data<=q->data)
		{
			t=p;
			p=p->next;
			t->next=A->next;
			A->next=t;						
		}
		else
		{
			t=q;
			q=q->next;
			t->next=A->next;
			A->next=t;			
		}	
	}
	while(p)
	{
		t=p;
		p=p->next;
		t->next=A->next;
		A->next=t;
	}
	while(q)
	{
		t=q;
		q=q->next;
		t->next=A->next;
		A->next=t;
	}
	return true;
}