#include <iostream>
using namespace std;

typedef struct lnode
{
	int data;
	struct lnode* next;
}LNODE;

typedef struct list
{
	LNODE* head;
	LNODE* tail;
}LIST;


LIST mergeA(LIST lst1, LIST lst2);
LIST mergeB(LIST lst1, LIST lst2);
LIST mergeC(LIST lst1, LIST lst2);
void makeEmptyList(LIST &newList);
void insertDataToEndList(LIST &lst, int data);
LNODE* createNewListNode(int data, LNODE* next);
void insertNodeToEndList(LIST &lst, LNODE* newTail);
bool isEmptyList(LIST lst);
void printList(LIST lst);


void main()
{
	{
		LIST lst1, lst2, newList;

		makeEmptyList(lst1);
		makeEmptyList(lst2);

		insertDataToEndList(lst1, 2);
		insertDataToEndList(lst1, 5);
		insertDataToEndList(lst1, 7);
		insertDataToEndList(lst1, 11);

		insertDataToEndList(lst2, 1);
		insertDataToEndList(lst2, 6);
		insertDataToEndList(lst2, 9);

		newList = mergeA(lst1, lst2);
		printList(newList);

		cout << endl << endl;

		system("pause");
	}
	{
		LIST lst1, lst2, newList;

		makeEmptyList(lst1);
		makeEmptyList(lst2);

		insertDataToEndList(lst1, 2);
		insertDataToEndList(lst1, 5);
		insertDataToEndList(lst1, 7);
		insertDataToEndList(lst1, 11);

		insertDataToEndList(lst2, 1);
		insertDataToEndList(lst2, 6);
		insertDataToEndList(lst2, 9);

		newList = mergeB(lst1, lst2);
		if (isEmptyList(newList))
		{
			cout << "is empty list" << endl;
		}
		else
		{
			printList(newList);
		}
		cout << endl << endl;

		system("pause");
	}

}




LIST mergeA(LIST lst1, LIST lst2)
{
	LNODE* curr1 = lst1.head;
	LNODE* curr2 = lst2.head;

	LIST newList;
	makeEmptyList(newList);

	while (curr1 != NULL && curr2 != NULL)
	{
		if (curr1->data < curr2->data)
		{
			insertDataToEndList(newList, curr1->data);
			curr1 = curr1->next;
		}
		else
		{
			insertDataToEndList(newList, curr2->data);
			curr2 = curr2->next;
		}
	}

	while (curr1 != NULL)
	{
		insertDataToEndList(newList, curr1->data);
		curr1 = curr1->next;
	}

	while (curr2 != NULL)
	{
		insertDataToEndList(newList, curr2->data);
		curr2 = curr2->next;
	}

	return newList;
}
/*
1 2 5 6 7 9 11

Press any key to continue . . .

*/


LIST mergeC(LIST lst1, LIST lst2)
{
	LIST newList;
	makeEmptyList(newList);

	if (isEmptyList(lst1) && !isEmptyList(lst2))
	{
		newList = lst2;
		return newList;
	}
	else if (!isEmptyList(lst1) && isEmptyList(lst2))
	{
		newList = lst1;
		return newList;
	}
	else if (isEmptyList(lst1) && isEmptyList(lst2))
	{
		return newList;
	}
	else
	{
		if (lst1.head->data < lst2.head->data)
		{
			insertDataToEndList(newList, lst1.head->data);
			lst1.head = lst1.head->next;
			mergeC(lst1, lst2);
		}
		else (lst2.head->data < lst1.head->data);
		{
			insertDataToEndList(newList, lst2.head->data);
			lst2.head = lst2.head->next;
			mergeC(lst1, lst2);
		}
	}
}


void makeEmptyList(LIST &lst)
{
	lst.head = lst.tail = NULL;
}

void insertDataToEndList(LIST &lst, int data)
{
	LNODE* newTail;
	newTail = createNewListNode(data, NULL);
	insertNodeToEndList(lst, newTail);
}


LNODE* createNewListNode(int data, LNODE* next)
{
	LNODE* res;
	res = new LNODE;
	res->data = data;
	res->next = next;
	return res;
}

void insertNodeToEndList(LIST &lst, LNODE* newTail)
{
	if (isEmptyList(lst))
		lst.head = lst.tail = newTail;
	else
	{
		lst.tail->next = newTail;
		lst.tail = newTail;
	}
	lst.tail->next = NULL;
}

bool isEmptyList(LIST lst)
{
	if (lst.head == NULL)
		return true;
	else
		return false;
}

void printList(LIST lst)
{
	LNODE *curr = lst.head;

	while (curr != NULL)
	{
		cout << curr->data << " ";
		curr = curr->next;
	}
}