#include <iostream>
#include <utility>

struct Node
{
	int data;
	Node *next;
};

class LinkedList
{
private:
	Node *first;
	Node *last;
public:
	LinkedList();
	LinkedList(const LinkedList &src);
	LinkedList(int A[], int num);
	~LinkedList();

	LinkedList& operator=(const LinkedList &rhs);

	void Display() const;
	void Merge(LinkedList &b);
};

// Create Linked List using default values
LinkedList::LinkedList()
	: first(NULL), last(NULL)
{
}

// Create Linked List using Array
LinkedList::LinkedList(int A[], int n)
	: first(NULL), last(NULL)
{
	Node **p = &first;

	for (int i = 0; i < n; ++i)
	{
		Node *t = new Node;
		t->data = A[i];
		t->next = NULL;

		*p = t;
		p = &(t->next);

		last = t;
	}
}

// Create Linked List by copying another Linked List
LinkedList::LinkedList(const LinkedList &src)
	: first(NULL), last(NULL)
{
	Node **p = &first;

	for (Node *tmp = src.first; tmp; tmp = tmp->next)
	{
		Node* t = new Node;
		t->data = tmp->data;
		t->next = NULL;

		*p = t;
		p = &(t->next);

		last = t;
	}
}

// Deleting all Node in Linked List
LinkedList::~LinkedList()
{
	Node *p = first;

	while (p)
	{
		Node *tmp = p;
		p = p->next;
		delete tmp;
	}
}

// Update Linked List by copying another Linked List
LinkedList& LinkedList::operator=(const LinkedList &rhs)
{
	if (&rhs != this)
	{
		LinkedList tmp(rhs);
		std::swap(tmp.first, first);
		std::swap(tmp.last, last);
	}
	return *this;
}

// Displaying Linked List
void LinkedList::Display() const
{
	if (first)
	{
		std::cout << first->data;
		for (Node *tmp = first->next; tmp; tmp = tmp->next)
			std::cout << " " << tmp->data;
	}
	else
	{
		std::cout << "(empty)";
	}
	std::cout << std::endl;
}

// Merge two linked list
void LinkedList::Merge(LinkedList& b)
{
	if ((&b == this) || (!b.first))
		return;

	if (!first)
	{
		first = b.first; b.first = NULL;
		last = b.last; b.last = NULL;
		return;
	}

	// Store first pointer of Second Linked List
	Node *second = b.first;
	Node *third, **tmp = &third;

	// We find first Node outside loop, smaller number, so Third pointer will store the first Node
	// Then, we can only use tmp pointer for repeating process inside While loop
	// Use while loop for repeating process until First or Second hit NULL
	do
	{
		// If first Node data is smaller than second Node data
		if (first->data < second->data)
		{
			*tmp = first;
			tmp = &(first->next);
			first = first->next;
		}
		// If first Node data is greater than second Node data
		else
		{
			*tmp = second;
			tmp = &(second->next);
			second = second->next;
		}
		*tmp = NULL;
	}
	while (first && second);

	// Handle remaining Node that hasn't pointed by Last after while loop
	*tmp = (first) ? first : second;

	// Change first to what Third pointing at, which is First Node
	first = third;	

	// Change last pointer from old first linked list to new last Node, after Merge
	Node *p = first;
	while (p->next)
	{
		p = p->next;
	}	
	last = p;
	
	// Destroy second linked list because every Node it's now connect with first linked list
	// This also prevent from Double free()
	b.first = b.last = NULL;
}

int main()
{
	int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
	int arr2[] = {2, 6, 10, 16, 18, 22, 24};
	int size1 = sizeof(arr1) / sizeof(arr1[0]);
	int size2 = sizeof(arr2) / sizeof(arr2[0]);
	
	LinkedList l1(arr1, size1);
	LinkedList l2(arr2, size2);
	LinkedList l3(l1);
	LinkedList l4;

	std::cout << "before:" << std::endl;
	std::cout << "l1: "; l1.Display();
	std::cout << "l2: "; l2.Display();
	std::cout << "l3: "; l3.Display();
	std::cout << "l4: "; l4.Display();

	// Merge two linked list, pass l4 as reference
	l3.Merge(l2);

	// Copy a linked list
	l4 = l3;

	std::cout << std::endl;
	std::cout << "after:" << std::endl;
	std::cout << "l1: "; l1.Display();
	std::cout << "l2: "; l2.Display();
	std::cout << "l3: "; l3.Display();
	std::cout << "l4: "; l4.Display();

	return 0;
}