#include <iostream>

using namespace std;

struct List {
	int a;
	List *next;
};
struct Double_List {//структура данных
	int Data; //информационное поле
	Double_List *Next, //адресное поле
		*Prior; //адресное поле
};
Double_List *Head; //указатель на первый элемент списка
Double_List *Current;
//указатель на текущий элемент списка (при необходимости)
struct Circle_Single_List {
	int Data;
	Circle_Single_List* Next;
};
Circle_Single_List *Head_circ;
Circle_Single_List *Loop;
class _List {
public:
	List* newList;
	_List() {
		Head = NULL;
		newList = NULL;
		Head_circ = NULL;
	}
	void additem(int d);
	void additem2(int, Double_List*);
	void connect(_List &list);
	void sort(List *, List*);
	void sort2(Double_List *, Double_List*);
	void Prints();
	void clear();
	void Print_Double_List();
	void Make_Circle_Single_List(int d, Circle_Single_List* Loop);
	void Print_Circle_Single_List(Circle_Single_List* Head);
	void Sort_Circle_List(Circle_Single_List*, Circle_Single_List*);
};
int main() {
	_List u, u1, u2; Double_List* List2;
	int n(0),el(0), answ(0);//размер первого списка
	cout << "Menu: \n1.odnonapravlenii\n2.dvunapravleni\n3.ciklicheski\n"; cin >> answ;
	switch (answ) {
	case 1:
		cout << "Enter size of list 1: "; cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> el;
			u.additem(el);
		}
		cout << "Enter size of list 2:"; cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> el;
			u1.additem(el);
		}
		u2.connect(u);
		u2.connect(u1);
		u2.sort(u.newList, u1.newList);
		u2.Prints();
		u2.clear();
		break;
	case 2:
		cout << "Enter size of list 1: "; cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> el;
			u.additem2(el, Current);
		}
		cout << "Enter size of list 2:"; cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> el;
			u1.additem2(el, Current);
		}
		u2.connect(u);
		u2.connect(u1);
		u2.sort2(Head, Head);
		u2.Print_Double_List();
		u2.clear();
		break;
	case 3:
		cout << "Enter size of list 1: "; cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> el;
			u.Make_Circle_Single_List(el, Loop);
		}
		cout << "Enter size of list 2:"; cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> el;
			u1.Make_Circle_Single_List(el, Loop);
		}
		u2.connect(u);
		u2.connect(u1);
		u2.Sort_Circle_List(Head_circ, Head_circ);
		u2.Print_Circle_Single_List(Head_circ);
		break;
	default:cout << "\aError, invalid number\n"; break;
	}
	system("pause");
	return 0;
}
void _List::additem(int d) {
	List* createList = new List;
	createList->a = d;
	createList->next = NULL;
	List *x;//вспомогательный указатель
	if (newList != NULL) {
		x = newList;
		while ((x->next) != NULL) {
			x = x->next;
		}
		x->next = createList;
	}
	else {
		newList = createList;
	}
}

void _List::Prints() {
	cout << "Spisok: =";
	while (newList) {
		cout << newList->a << " ";
		newList = newList->next;
	}
}
void _List::Print_Double_List() {
	cout << "Spisok: =";
	while (Head) {
		cout << Head->Data << " ";
		Head = Head->Next;
	}
}
void _List::sort(List *node, List *node2) {
	for (node = newList; node; node = node->next)
		for (node2 = newList; node2; node2 = node2->next)
			if (node->a < node2->a) { // если число из node меньше числа из node2 то переставляем их
				int i = node->a;
				node->a = node2->a;
				node2->a = i;
			}
}
void _List::sort2(Double_List *node, Double_List *node2) {
	for (node = Head; node; node = node->Next)
		for (node2 = Head; node2; node2 = node2->Next)
			if (node->Data < node2->Data) { // если число из node меньше числа из node2 то переставляем их
				int i = node->Data;
				node->Data = node2->Data;
				node2->Data = i;
			}
}
void _List::connect(_List &list) {
	List* x = list.newList;
	while (x != NULL) {
		additem(x->a);
		x = x->next;
	}
}
void _List::additem2(int d, Double_List * Prior) {
	Double_List* createList = new Double_List;
	createList->Data = d;
	createList->Prior = Prior;
	createList->Next = NULL;
	Double_List *x;//вспомогательный указатель
	if (Head != NULL) {
		x = Head;
		while ((x->Next) != NULL) {
			x = x->Next;
		}
		x->Next = createList;
	}
	else {
		Head = createList;
	}
}
//создание циклического однонаправленного списка
void _List::Make_Circle_Single_List(int d, Circle_Single_List* Loop) {
	Circle_Single_List* createList = new Circle_Single_List;
	createList->Data = d;
	createList->Next = NULL;
	Circle_Single_List *x;//вспомогательный указатель
	if (Loop == NULL) Loop = createList;
	if (Head_circ != NULL) {
		x = Head_circ;
		while ((x->Next) != NULL) {
			x = x->Next;
		}
		x->Next = createList;
	}
	else {
		Head_circ = Loop;
	}
}
//печать циклического однонаправленного списка
void _List::Print_Circle_Single_List(Circle_Single_List* Head) {
	Circle_Single_List* ptr = Head;
	//вспомогательный указатель
	do {
		cout << ptr->Data << "\t";
		ptr = ptr->Next;

	} while (ptr);
	cout << "\n";
}

void _List::Sort_Circle_List(Circle_Single_List* node, Circle_Single_List *node2) {
	for (node = Head_circ; node; node = node->Next)
		for (node2 = Head_circ; node2; node2 = node2->Next)
			if (node->Data < node2->Data) { // если число из node меньше числа из node2 то переставляем их
				int i = node->Data;
				node->Data = node2->Data;
				node2->Data = i;
			}
}
void _List::clear() {
	if (newList != NULL) {
		clear();
		delete newList;
	}
}