[数据结构与算法]7-52 两个有序链表序列的交集 (20 分)大规模数据的测试点

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

输入格式:

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

输出格式:

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

输入样例:

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

结尾无空行

输出样例:

2 5

结尾无空行

? 写这个的时候不想用list容器，采用malloc方法，题目中的关键信息开始的时候没解读到，比如那个非降序的信息不知道怎么用，这个写在代码注释中了；

? 还有那个交集的定义和数学的交集也有所不同，交集内可以有重复元素，但重复的个数是这两个链表中这个元素的最少个数，比如1中有2个，2中有3个，那么重复个数就是2个。搞清楚这个之后，就理解了。

举个例子：

样例输入：
1?2?3?3?4?4 5 6 -1
1?1?2?2?3?3?4?-1
样例输出：
1?2?3?3?4

#include<iostream>
using namespace std;

class Node
{
public:
	int m_num;
	Node*  m_next;
};
typedef Node* ptr;
int main()
{
	ptr  p1 = NULL, p2 = NULL, p3 = NULL, p = NULL, pre = NULL;
	int temp;
	while (cin >> temp&&temp != -1)
	{  
		p = (ptr)malloc(sizeof(Node));
		p->m_num = temp;
		p->m_next = NULL;
		if (pre != NULL)
		{
			pre->m_next = p;
		}
		pre = p;
		if (p1==NULL)
			p1 = p;
	}
	pre = NULL;
	while (cin >> temp && temp != -1)
	{
		p = (ptr)malloc(sizeof(Node));
		p->m_num = temp;
		p->m_next = NULL;
		if (pre != NULL)
		{
			pre->m_next = p;
		}
		pre = p;
		if (p2 == NULL)
			p2 = p;
	}
	pre = NULL;//勿漏
	p = p2;
	while (p1 != NULL)  //总结该大规模数据的测试点就是遇到过的下次就不再比较，从下一位开始
	{
		if (p != NULL)  //如果p已经为NULL 用p->m_num就是非法的
		{
			if (p1->m_num == p->m_num)
			{
				ptr q = (ptr)malloc(sizeof(Node));
				q->m_num = p->m_num;
				q->m_next = NULL;
				if (pre != NULL)
				{
					pre->m_next = q;  //不用list容器就需要记录前一个结点，再更新此记录结点
				}
				pre = q;
				if (p3 == NULL)
					p3 = q;
				p1 = p1->m_next;
				p = p->m_next; //这句也是关键点，会不会重复的问题
			}
			else if (p1->m_num > p->m_num)
			{
				p = p->m_next;
			}
			else
			{
				p1 = p1->m_next;
			}
		}
		else
		{
			break;
		}
	}
	if (p3 == NULL)
		cout << "NULL" << endl;
	else
	{
		cout << p3->m_num;
		p3 = p3->m_next;
		while (p3 != NULL)
		{
			cout <<" " <<p3->m_num ;
			p3 = p3->m_next;
		}
	}
	system("pause");
	return 0;
}