#include <stdio.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
struct Node
{
	int data;
	Node* next;
	Node* prev;

	Node(int _data)
	{
		data = _data;
		next = NULL;
		prev = NULL;
	}

	Node(Node* _node)
	{
		data = _node->data;
		next = _node->next;
		prev = _node->prev;
	}
};

struct DLlist
{
	Node* head;

	DLlist()
	{
		head = NULL;
	};


	DLlist(int _data)
	{
		head = new Node(_data);
		head->next = NULL;
		head->prev = NULL;
	}

	DLlist(DLlist* _list)
	{
		Node* current = _list->head;
		while (current != NULL)
		{
			push_back(current->data);
			current = current->next;
		}
	}

	void DeleteList()
	{
		Node* tmp = head;
		while (head != NULL)
		{
			tmp = head->next;
			delete head;
			head = tmp;
		}
	}

	void Print()
	{
		Node* current = head;
		while (current != NULL)
		{
			cout << current->data << " ";
			current = current->next;
		}
		cout << endl;
	}

	void push_back(int _data)
	{
		Node* current;
		Node* new_node = new Node(_data);
		if (head == NULL)
		{
			head = new_node;
			head->next = NULL;
			return;
		}
		current = head;
		while (current->next != NULL)
			current = current->next;
		current->next = new_node;
		new_node->prev = current;
		new_node->next = NULL;
	}

	void merge(DLlist& list)
	{
		int main; // Переключатель очереди, определяет какой лист сейчас будет добавлять.
		int size_this;
		int size_list;
		bool HeadChanged = false;
		Node* current_this; // Итератор первого листа
		Node* current_list; // Итератор второго листа

		current_this = head;
		current_list = list.head;
		main = 0;
		size_this = 1;
		size_list = 1;
		while ((current_this != NULL)||(current_list != NULL)) // Пока хотя бы в одном листе есть данные
		{
			if (main % 2 == 0) // Если остаток от деления на 2 == 0, тогда
			{
				if (current_this != NULL)
				{
					Node* buffer = current_this->next;
					size_this = size_this++;
					if (current_list != NULL)//Если в другом еще есть данные, тогда
					{
						current_this->next = current_list; //Присоединяем данные из другого листа в этот
						current_list->prev = current_this; //Обновляем prev
						current_this = buffer; //Идем дальше
						if (current_list->prev == head)
						{
							if (HeadChanged == false)
							{
								list.head = head;
								HeadChanged = true;
							}
						}
					}
					else //Иначе, раз в другом данных нет, значит, этот лист имеет "лишние" члены. АХАХАХАХ ЧЛЕНЫ АХАХАХХА.
					{
						cout << "Extra member:" << current_this->data << endl;
						current_this = current_this->next;
					}
					//if (current_this->next != NULL) // Если есть следующий элемент, то переключаемся на него
					//	current_this = current_this->next;
					//else
					//	current_this = NULL;

				}
				main = main++;
			}
			else // Иначе, если == 1, тогда
			{
				if (current_list != NULL)
				{
					Node* buffer = current_list->next;
					size_list = size_list++;
					if (current_this != NULL)
					{
						current_list->next = current_this;
						current_this->prev = current_list;
						current_list = buffer;
					}
					else
					{
						cout << "Extra member:" << current_list->data << endl;
						current_list = current_list->next;
					}
					//if (current_list->next != NULL) // Если есть следующий элемент, то переключаемся на него
					//	current_list = current_list->next;
					//else
					//	current_list = NULL;
				}
				main = main++;
			}
		}
		cout << "Total = " << abs(size_list - size_this) << endl;
	}
};

void main()
{
	DLlist A;
	DLlist B;
	for (int i = 1; i < 4; i++)
	{
		A.push_back(i);
	}
	A.Print();

	for (int i = 1; i < 5; i++)
	{
		B.push_back(i*10);
	}
	B.Print();
	A.merge(B);
	A.Print();
	B.Print();

	A.DeleteList();
}