//已知两个非降序链表序列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;
struct node
{
int num;
node* next;
};
int static counter1 = 0;
void compare(node*head1,node*head2,node*&head3)
{
node* s;
node* q = NULL;
node* cur = head2;
while (head1)
{
while (cur)
{
if (head1->num == cur->num)
{
counter1++;
s = new node;
s->num = head1->num;
s->next = NULL;
if (head3 == NULL)
{
head3 = s;
}
else q->next = s;
q = s;
}
cur = cur->next;
}
head1 = head1->next;
cur = head2;
}
}
void show(node *head3)
{
int counter2 = 0;
if (head3 == NULL)
cout << "NULL" ;
else {
while (head3)
{
counter2++;
if (counter2 < counter1) {
cout << head3->num << ' ';
}
else cout << head3->num;
head3 = head3->next;
}
}
}
int main()
{
node* head1 = NULL;
node* head2 = NULL;
node* head3 = NULL;
int k, m, n;
node* s;
node* q = NULL;
cin >> k;
while (k != -1)
{
s = new node;
s->num = k;
s->next = NULL;
if (head1 == NULL)
{
head1 = s;
}
else q->next = s;
q = s;
cin >> k;
}
node* r;
node* p = NULL;
cin >> m;
while (m != -1)
{
r = new node;
r->num = m;
r->next = NULL;
if (head2 == NULL)
{
head2 = r;
}
else p->next = r;
p = r;
cin >> m;
}
compare(head1, head2, head3);
show(head3);
return 0;
}