7-4 两个有序链表合并（新表不含重复元素）
分数 20
作者 陈晓梅
单位 广东外语外贸大学
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
要求S3中没有重复元素。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出合并后新的非降序链表，要求链表中没有重复元素。数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
在这里给出一组输入。例如：
1 3 3 5 8 -1
2 3 4 6 8 10 -1
输出样例:
在这里给出相应的输出。例如：
1 2 3 4 5 6 8 10
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
```c++
#include <iostream>
using namespace std;
typedef struct Lnode
{
int data;
struct Lnode *next;
} Lnode, *Linklist;
void creat_a(Linklist &La)
{
La = new Lnode;
La->next = NULL;
Linklist p, q = La;
while (1)
{
p = new Lnode;
cin >> p->data;
if (p->data == -1)
{
return;
}
p->next = NULL;
q->next = p;
q = p;
}
}
void creat_b(Linklist &Lb)
{
Lb = new Lnode;
Lb->next = NULL;
Linklist p, q = Lb;
while (1)
{
p = new Lnode;
cin >> p->data;
if (p->data == -1)
{
return;
}
p->next = NULL;
q->next = p;
q = p;
}
}
void init (Linklist &Lc)
{
Lc = new Lnode;
Lc->next = NULL;
}
void Mergelist(Linklist &La, Linklist &Lb, Linklist &Lc)
{
Linklist pa, pb, pc;
pa = La->next;
pb = Lb->next;
pc = Lc = La;
while ( pa && pb )
{
if ( pa->data <= pb->data )
{
if ( pc->data != pa->data )
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pa = pa->next;
}
}
else
{
if ( pc->data != pb->data )
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
else
{
pb = pb->next;
}
}
}
if ( pa == NULL )
{
while ( pb != NULL )
{
if ( pc->data != pb->data )
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
else
{
pb = pb->next;
}
}
}
else
{
while ( pa != NULL )
{
if ( pc->data != pa->data )
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pa = pa->next;
}
}
}
delete Lb;
}
void Print(Linklist Lc)
{
Linklist p = Lc->next;
if ( p == NULL )
{
cout << "NULL";
}
while (p != NULL)
{
cout << p->data;
if (p->next != NULL)
{
cout << " ";
}
p = p->next;
}
}
int main()
{
Linklist La, Lb, Lc;
creat_a(La);
creat_b(Lb);
init(Lc);
Mergelist(La, Lb, Lc);
Print(Lc);
printf ("\n");
return 0;
}
```
