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

寻寻寻寻

已于 2024-09-12 14:35:29 修改

阅读量321

点赞数 1

分类专栏：原创编程题AC代码文章标签：数据结构 c语言链表算法

于 2020-11-30 20:34:43 首次发布

本文链接：https://blog.csdn.net/SDU_st/article/details/110405035

版权

原创编程题AC代码专栏收录该内容

14 篇文章

订阅专栏

该博客介绍如何处理两个非降序链表序列的交集问题。通过算法设计，实现找到这两个序列共有的元素，并以非降序方式输出。输入和输出格式以及示例数据也一同给出。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

7-2 两个有序链表序列的交集 (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<malloc.h>
#include<stdlib.h>
#define OK 1
#define FALSE 0
typedef int Status;
typedef int Elemtype;
typedef struct Node {
	Elemtype data;
	Node *next;
} Node,*LinkList;
Status CreatList(LinkList &L);
void MergeList(LinkList &L1,LinkList &L2,LinkList &L);
void OutPut(LinkList &L);
void IntersectList(LinkList &L1,LinkList &L2,LinkList &L);
int main() {
//	freopen ("in.txt","r",stdin);
	LinkList L1,L2,L;
	CreatList(L1);
	CreatList(L2);
	IntersectList(L1,L2,L);
	OutPut(L);
	return 0;
}
void IntersectList(LinkList &L1,LinkList &L2,LinkList &L){
	L=(Node*)malloc(sizeof(Node));
	L->next=NULL;
	 Node * la,*lb,*lc;
    lc =L ;
    la = L1->next;
    lb = L2->next;

    while(la && lb) {
        if(la->data == lb->data) {

            lc->next = la;
            lc = la;
            la = la->next;
            lb = lb->next;
        }
        else if(la->data > lb->data) {
            lb = lb->next;
        }
        else{
            la = la->next;
        }
    }
}
Status CreatList(LinkList &L) {
	Node *forp,*endp;
	L=(Node*)malloc(sizeof(Node));
	if(!L)exit(FALSE);
	L->next=NULL;
	int a;
	forp=L;
	while(scanf("%d",&a)!=EOF) {
		if(a==-1)return 1;
		endp=(Node*)malloc(sizeof (Node));
		if(!endp)exit(FALSE);
		forp->next=endp;
		endp->data=a;
		endp->next=NULL;
		forp=endp;
	}
	return FALSE;
}
void MergeList(LinkList &L1,LinkList &L2,LinkList &L) {
	Node *a,*b,*c;
	L=(Node*)malloc(sizeof(Node));
	L->next=NULL;
	a=L1->next;
	b=L2->next;
	c=L;
	while(a&&b) {
		if(a->data>b->data) {
			c->next=b;
			b=b->next;
			c=c->next;
		} else {
			c->next=a;
			a=a->next;
			c=c->next;
		}
	}
	c->next=a?a:b;
	free(a);
}
void OutPut(LinkList &L) {
	if(L->next==NULL)printf("NULL");
	else {
		Node *pp=L->next;
		printf("%d",pp->data);
		pp=pp->next;
		while(OK) {	printf(" %d",pp->data);
			if(pp->next==NULL)break;
			pp=pp->next;
		}
	}
}