将两个递增的有序链表合并为一个递增的有序链表.【数据结构】【线性表】-Toy模板网

这篇具有很好参考价值的文章主要介绍了将两个递增的有序链表合并为一个递增的有序链表.【数据结构】【线性表】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

编写一个函数完成如下功能：将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来的链表空间，不另外占用其他的存储空间。表中不允许有重复的数据。

要求，在主函数中调用上面的函数测试。

提示：还需要定义其他函数，比如初始化链表，构造单链表，输出单链表。

#include<iostream>
using namespace std;
//定义单链表
typedef struct  LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
//初始化单链表
int InitList(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
	return 0;
}
//构造单链表
int ConsList(LinkList &L)
{
	cout << "输入赋值的个数：" ;
	int n;
	cin >> n;
	LinkList r = L;
	cout << "输入链表：";
	for (int i = 0; i < n; i++) {
		LinkList p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}
	return 0;
}

//合并
void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC){
	LinkList pa = LA->next;     
	LinkList pb = LB->next;
	LC = LA;
	LinkList pc = LC;
	while (pa && pb)
	{
		if (pa->data < pb->data)
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else if(pb->data<pa->data)
		{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
		else
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			LinkList p = pb;
			pb = pb->next;
			delete p;
		}
	}
	if (pa) 
	{
		pc->next = pa;
	}
	else
	{
		pc->next = pb;
	}
	delete LB;
}
//输出链表
void print(LinkList L){
	LinkList p = L->next;
	while(p)
	{
		cout << p->data<<" ";
		p = p->next;
	}
}

int main() 
{
	cout << "请输入第一个递增的链表："<<endl;
	LinkList LA, LB, LC;
	InitList(LA);
	ConsList(LA);
	cout << "请输入第二个递增的链表："<<endl;
	InitList(LB);
	ConsList(LB);
	MergeList_L(LA,LB,LC);
	cout << "合并为一个递增的链表后为：";
	print(LC);
	return 0;
}