#include <iostream>
#include <string>
#include <time.h>
using namespace std;
const int res = -9999999;

struct NOT
{
	int date;
	NOT* next;
};

void add(NOT* &NN, int d)
{
	NOT* tmp = new NOT;
	tmp->date = d;
	tmp->next = NN;
	NN = tmp;
}

void _delete(NOT* &NN, int key)
{
	NOT *prev = NULL;
	NOT *vsp = NN;
	while (vsp->next!=NULL) vsp = vsp->next;
	NOT *End = vsp;
	if ((NN == End) && (NN!=NULL))
	{
		NN = NULL;
	}
	else if (NN!=NULL)
	{
		vsp = NN;
		while (vsp!=NULL)
		{
			NOT* tmp = vsp->next;
			if (vsp->date == key)
			{
				if (prev)
				{
					prev->next = vsp->next;
				}
				delete vsp;
			}
			else
			{
				prev = vsp;
			}
			vsp = tmp;
		}
	}
}

void seek_simillar(NOT* &M, NOT* &M1, NOT* &M2)
{
	for (NOT* vsp1 = M1; vsp1!=NULL; vsp1 = vsp1->next)
	{
		for (NOT* vsp2 = M2; vsp2!=NULL; vsp2 = vsp2->next)
		{
			if (vsp1->date == vsp2->date)
			{
				bool k=false;
				for (NOT* vsp = M; (vsp!=NULL)&&(k==false); vsp = vsp->next)
				{
					k = vsp->date == vsp1->date;
				}
				if (k==false)
				{
					NOT* tmp = new NOT;
					tmp->date = vsp1->date;
					tmp->next = M;
					M = tmp;
				}
			}
		}
	}
}

void seek_atleastone(NOT* &M, NOT* &M1, NOT* &M2)
{
	for (NOT* vsp1 = M1; vsp1!=NULL; vsp1 = vsp1->next)
	{
		bool k=false;
		for (NOT* vsp = M; (vsp!=NULL)&&(k==false); vsp = vsp->next)
		{
			k = vsp->date == vsp1->date;
		}
		if (k==false)
		{
			NOT* tmp = new NOT;
			tmp->date = vsp1->date;
			tmp->next = M;
			M = tmp;
		}
	}
	for (NOT* vsp2 = M2; vsp2!=NULL; vsp2 = vsp2->next)
	{
		bool k=false;
		for (NOT* vsp = M; (vsp!=NULL)&&(k==false); vsp = vsp->next)
		{
			k = vsp->date == vsp2->date;
		}
		if (k==false)
		{
			NOT* tmp = new NOT;
			tmp->date = vsp2->date;
			tmp->next = M;
			M = tmp;
		}
	}
}

void seek_onenottwo(NOT* &M, NOT* &M1, NOT* &M2)
{
	for (NOT* vsp1 = M1; vsp1!=NULL; vsp1 = vsp1->next)
	{
		bool k=false;
		for (NOT* vsp = M; (vsp!=NULL)&&(k==false); vsp = vsp->next)
		{
			k = vsp->date == vsp1->date;
		}
		if (k==false)
		{
			NOT* tmp = new NOT;
			tmp->date = vsp1->date;
			tmp->next = M;
			M = tmp;
		}
	}
	for (NOT* vsp1=M1; vsp1!=NULL; vsp1=vsp1->next)
	{
		for (NOT* vsp2=M2; vsp2!=NULL; vsp2=vsp2->next)
		{
			if (vsp1->date == vsp2->date)
			{
				for (NOT* vsp = M; vsp!=NULL; vsp=vsp->next)
				{
					if (vsp->date == vsp1->date) vsp->date = res;
				}
			}
		}
	}
	_delete(M, res);
}

void print(NOT* &NN)
{
	NOT* vsp = NN;
	if (NN == NULL) cout<<"Пусто"<<endl;
	else
	while (vsp!=NULL)
	{
		cout << vsp->date << endl;
		vsp = vsp->next;
	}
}

void menu(NOT* &M, NOT* &M1, NOT* &M2)
{
	int a;
	cout<<"Меню"<<endl<<"1. Элементы входят хотя бы в один из списков M1 и M2"<<endl<<"2. Элементы входят и в M1, и в M2 одновременно"<<endl<<"3. Элементы входят в M1, но не входят в M2"<<endl;
	cout<<"Ваш вариант: ";
	cin>>a;
	switch(a)
	{
	case (1):
		{
			seek_atleastone(M, M1, M2);
			cout<<"Список M:"<<endl;
			print(M);
			break;
		}
	case (2):
		{
			seek_simillar(M, M1, M2);
			cout<<"Список M:"<<endl;
			print(M);
			break;
		}
	case (3):
		{
			seek_onenottwo(M, M1, M2);
			cout<<"Список M: "<<endl;
			print(M);
			break;
		}
	}
}

int main()

{
	srand(time(0));
	setlocale(0, "Rus");
	NOT* M = NULL; NOT* M1 = NULL; NOT* M2 = NULL;
	for (int i=0; i<5; i++)
	{
		add(M1, rand()%8);
		add(M2, rand()%8);
	}
	cout <<"Список М1: "<<endl;
	print(M1);
	cout<<"Список M2: "<<endl;
	print(M2);
	menu(M, M1, M2);
	system("pause");
	return 0;
}