将两个递增的有序链表合并成一个递增的有序链表（CPP版）
#include<iostream>
using namespace std;
//自定义链表的存储结构
typedef struct LNode {
int date;
struct LNode *next;
}LNode,*LinkList;
//创建链表
int CreatList(LinkList &L, int n) {
LNode *p, *r;
L = new LNode;
L->next = NULL;
r = L;
for (int i = 0;i < n;i++) {
p = new LNode;
cin >> p->date;
p->next = NULL;
r->next = p;
r = p;
}
return 0;
}
//打印链表
void PrintList(LinkList L) {
LinkList p;
p = L->next;
while (p) {
cout << p->date << " ";
p = p->next;
}
cout << endl;
}
//链表合并，合并链表 La 和 Lb，合并后的新表使用头指针 Lc 指向
void MergeList(LinkList &LA, LinkList &LB, LinkList &LC) {
LNode *pa, *pb, *pc;
//pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点
pa = LA->next;
pb = LB->next;
///用 La 的头结点作为 Lc 的头结点
LC = LA;
pc = LC;
//循环到LA和LB中数据全部遍历到
while (pa&&pb) {
///取较小者 La 中的元素，将 pa 链接在 pc 的后面，pa 指针后移
if (pa->date < pb->date){
pc->next = pa;
pc = pa;
pa = pa->next;
}
///取较小者 Lb 中的元素，将 pb 链接在 pc 的后面，pb 指针后移
else if (pa->date > pb->date) {
pc->next = pb;
pc = pb;
pb = pb->next;
}
else {
//相等时取 La 中的元素，删除 Lb 中的元素
pc->next = pa;
pc = pa;
pa = pa->next;
pb = pb->next;
}
}
//将非空集的剩余元素直接链接在LC表的最后
pc->next = pa ? pa:pb;
//释放 Lb 的头结点,堆区数据要及时释放
delete LB;
}
int main(){
LinkList LA, LB, LC;
int n;
cout << "请输入需要创建的LA链表的长度:" << endl;
cin >> n;
cout << "请依次输入数据，并以enter键分割数据" << endl;
CreatList(LA, n);
cout << "请输入需要创建的LB链表的长度:" << endl;
cin >> n;
cout << "请依次输入数据，并以enter键分割数据" << endl;
CreatList(LB, n);
cout << "当前LA链表为：" << endl;
PrintList(LA);
cout << "当前LB链表为：" << endl;
PrintList(LB);
MergeList(LA, LB, LC);
cout << "合并后的LC链表为：" << endl;
PrintList(LC);
system("pause");
return 0;
}