[数据结构与算法]用C++实现将两个递增链表合并为一个递增链表，不改变原来的存储空间，且不允许出现重复的元素

代码：

#include<iostream>
using namespace std;
typedef struct {
	int data;
} Data;

typedef struct LNode {
	Data elem;
	struct LNode* next;
}Lnode, * Linklist;

//单链表初始化
int Init_List(Linklist& L)//&L可以直接对L操作，这样不用返回结构体
{
	//L = (Linklist)malloc(sizeof(LNode));//开辟空间(C语言)
	//L=new Lnode; C++开辟空间
	L = new Lnode;
	L->next = NULL;//头结点指针域置空
	return 1;//初始化完毕
}

//后插法创建单链表
void Create_List(Linklist& L, int n)//n为输入元素的个数
{
	Linklist r;//创建尾指针
	r = L;//指向头结点
	for (int i = 0; i < n; i++)
	{
		Linklist p = new LNode;//开辟空间，P为结点
		cout << "输入第"<<i + 1 <<"个数据" << endl;;
		cin >> p->elem.data;
		p->next = NULL;
		r->next = p;//将新节点插入r之后
		r = p;//r指向新的尾节点
	}
}

void Merge_List(Linklist& La, Linklist& Lb, Linklist& Lc)
{//合并La和Lb，合并之后新表头用Lc指向
	Linklist pa = La->next;
	Linklist pb = Lb->next;
	//pa和pb分别是链表La和Lb的工作指针，初始化为相应链表的第一个节点
	Linklist pc;
	Lc = pc = La;//用La的头结点作为Lc的头结点
	while (pa && pb)
	{
		if (pa->elem.data < pb->elem.data)//到任意一个链表的尾结点结束
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;//取较小者中La中的元素，pa链接在pc的后面，pa指针后移
		}
		else if (pb->elem.data < pa->elem.data)
		{
			pc->next = pb;
			pc = pb;
			pb = pb->next;//
		}
		else
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			delete pb;
			//Linklist q = pb->next;
			//pb = q;//与free(pb)效果一样;
		}
	}
	pc->next = pa ? pa : pb;//插入剩余段
	delete Lb;//释放Lb的头结点
}
//打印函数
void Print_List(Linklist L)
{
	Linklist p = L;
	p = L->next;
	while (p)
	{
		cout << p->elem.data<<" ";
		p = p->next;
	}
}

int main()
{
	Linklist La, Lb, Lc;//创建两个链表
	//初始化
	Init_List(La);
	Init_List(Lb);
	//输入数据
	int num1, num2;
	cout << "分别输入两条链表数据个数" << endl;
	cin >> num1;
	cin >> num2;
	cout<< "第一个链表的数据" <<endl ;
	Create_List(La, num1);
	cout << "第二个链表的数据" << endl;
	Create_List(Lb, num2);
	Merge_List(La, Lb, Lc);
	cout << "两链表合并后数据为：" << endl;
	Print_List(Lc);
}