【目标500道第21道】2021-05-23 两个有序链表序列的交集（得18分）

本文主要是介绍【目标500道第21道】2021-05-23 两个有序链表序列的交集（得18分），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

//已知两个非降序链表序列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;
}

这篇关于【目标500道第21道】2021-05-23 两个有序链表序列的交集（得18分）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！