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

【目标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;
}
上一篇:十大经典排序之桶排序(C++实现)


下一篇:Java中使用jxl.jar将数据导出为excel文件