1-7 两个有序链表序列的交集 (20 分)

1-7 两个有序链表序列的交集 (20 分)
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

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

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

输入样例:
1 2 5 -1
2 4 5 8 10 -1
结尾无空行
输出样例:
2 5

这道题注意是有序链表，所以要找两个表中相等的元素就可以通过比大小，先找出两个表中第一个小元素，接着就在这个表中往前找，直到追上另一个表的第一个元素，这时如果相等的话就放到新链表中，如果大于第二个表的第一个元素了，第二个表再执行上述相同操作。

#include<stdio.h>
#include<stdlib.h>

typedef struct
{
    int data;
    struct Node *next;
}Node,*List;
List Create_List();
void printlist(List L);
void printlist(List L)
{
    int k=0;
    L=L->next;
    if(L==NULL)
        printf("NULL");
    else
    {
        while(L!=NULL)
        {
            if(k!=0)
                printf(" ");
                printf("%d",L->data);
            L=L->next;
            k=1;

        }
            printf("n");
    }
}
List Create_List()
{
    List L,s,r;
    int n;
    L=(List)malloc(sizeof(Node));
    L->next=NULL;
    r=L;

        scanf("%d",&n);
        while(n!=-1)
        {
              s=(List)malloc(sizeof(Node));
              s->data=n;
             r->next=s;
              r=s;
              scanf("%d",&n);
        }
        r->next=NULL;//采用尾插法的方式，记得最后尾指针置零
        return L;
}
int main()
{
   List L1,L2,p,q,L3,r,t;
   L1=(List)malloc(sizeof(Node));
   L1->next=NULL;
   L2=(List)malloc(sizeof(Node));
   L2->next=NULL;
   L1=Create_List();
   L2=Create_List();
   p=L1->next;
   q=L2->next;
   L3=(List)malloc(sizeof(Node));
   L3->next=NULL;
    r=L3;

    while(p!=NULL&&q!=NULL)
    {
   if(p->data<q->data)
    p=p->next;
   else if(p->data>q->data)
    q=q->next;
   else
   {
    r->next=p;
    r=p;
    p=p->next;
    q=q->next;
   }
    }
    r->next=NULL;
     printlist(L3);
}

最后

以上就是羞涩香烟为你收集整理的1-7 两个有序链表序列的交集 (20 分)的全部内容，希望文章能够帮你解决1-7 两个有序链表序列的交集 (20 分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。