博客

7-2 两个有序链表序列的交集 （20 分）

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出

NULL

。

输入样例:

1 2 5 -1
2 4 5 8 10 -1

输出样例:

2 5

#include <bits/stdc++.h>
using namespace std;
typedef struct Node* List;
struct Node
{
    int data;
    struct Node *next;
};

List init()
{
     List l;
     l = (List) malloc(sizeof (struct Node));
     if(!l)
     return NULL;
     l->next = NULL;
     return l;
}

void Insert(List L,int t)
{
    List p = (List) malloc(sizeof (struct Node));
    if(!p)
    return ;
    p->data =t;
    p->next = L->next;
    L->next = p;
    return ;
}
List Union(List l1,List l2,List l3)
{
    List q,p;
    p = l1->next;
    q = l2->next;
    while(p!=NULL&&q!=NULL)
    {
        //cout<<"ggg"<<endl;
        if(p->data<q->data)
        {
            q=q->next;
        }
        else if(p->data>q->data)
        {
            p=p->next;
        }
        else
        {
            Insert(l3,p->data);
            p=p->next;
            q=q->next;
        }
    }
    return l3;
}
int main()
{
    List l1,l2,l3;
    int t;
    l1=init();
    l2=init();
    l3=init();
    while(cin>>t&&t!=-1)
    {
        Insert(l1,t);
    }
    while(cin>>t&&t!=-1)
    {
        Insert(l2,t);
    }
    if(!l1->next||!l2->next)
    {
        cout<<"NULL"<<endl;
        return 0;
    }
    l3=Union(l1,l2,l3);
    if(!l3->next||!l3)
    {
        cout<<"NULL"<<endl;
        return 0;
    }
    for(l3=l3->next;l3->next!=NULL;l3=l3->next)
    {
        cout<<l3->data<<' ';
    }
    cout<<l3->data<<endl;

    return 0;
}

another:

#include <cstdio>
#include <list>
#include <iostream>
using namespace std;

int main()
{
    list<int>  list1;
    list<int>  list2;
    list<int>::iterator it,it1,it2;
    int val=0;
    bool flag = false;
    while(scanf("%d",&val),val!=-1)
        list1.push_back(val);
    while(scanf("%d",&val),val!=-1)
        list2.push_back(val);
    int t = 0;
    for (it1=list1.begin(),it2=list2.begin(); it1!=list1.end()&&it2!=list2.end();)
    {
        if (*it1 < *it2)
        {
            it1++;
        }
        else if (*it1 > *it2)
        {
            it2++;
        }
        else
        {
            if (flag)
                printf(" ");
            else
                flag = true;
            printf("%d",*it1);
            it2++;
            it1++;
            t = 1;
        }
    }
    if (list1.empty()||list2.empty()||t==0)
    {
        printf("NULL");
    }
    printf("\n");
    return 0;
}