已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。
输入样例:
1 2 5 -1
2 4 5 8 10 -1
输出样例:
2 5
#include <iostream>
using namespace std;
typedef struct Lnode
{
int data;
Lnode *next;
}Lnode, *Linklist;
void creat_a( Linklist &La )
{
Linklist p, q;
La = new Lnode;
La->next = NULL;
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 )
{
Linklist p, q;
Lb = new Lnode;
Lb->next = NULL;
q = Lb;
while(1)
{
p = new Lnode;
cin>>p->data;
if ( p->data == -1 )
{
return;
}
p->next = NULL;
q->next = p;
q = p;
}
}
void jiaoji ( Linklist &La, Linklist &Lb, Linklist &Lc )
{
Linklist pa, pb, q, r;
Lc = new Lnode;
Lc->next = NULL;
pa = La;
pb = Lb;
r = Lc;
while ( pa->next != NULL )
{
while ( pb->next != NULL )
{
if ( pa->next->data == pb->next->data )
{
q = new Lnode;
q->data = pb->next->data;
q->next = NULL;
r->next = q;
r = q;
}
pb = pb->next;
}
pa = pa->next;
}
}
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);
jiaoji (La, Lb, Lc);
Print (Lc);
return 0;
}