/*Problem description
	Given N natural number(s), separate 0's and bring them to the left side of the containers.
	Time Complexity  : O(n)
	Memory Complexity: O(1)
*/
#include <iostream>
using namespace std;

struct node {
	int data;
	node* nextNode = NULL;
};

class LinkedList {
public:
	~LinkedList();

	void addNode(int);				//Used to add more node
	void shiftZero();				//Wrapper function
	void display();					//Used to display the whole list

private:
	node * head = NULL;
	node * tail = NULL;
	int size = 0;

	void shiftZero(node*&);			//Main Shifter - Recursively called to shift all the zeros to the beginning of the list
};

int main() {
	LinkedList myList;
	int numOfNum = 0;
	cout << "Please enter number of numbers: ";
	cin >> numOfNum;

	cout << "Please enter " << numOfNum << " numbers: ";
	//Take the input and display the list
	for (int indx = 0; indx < numOfNum; indx++) {
		int temp;
		cin >> temp;
		myList.addNode(temp);
	}
	cout << endl;
	myList.display();

	//Shift zeros then display again
	myList.shiftZero();
	myList.display();

	return 0;
}

LinkedList::~LinkedList() {
	//Clean up after you play!
	node* current = head;
	while (current != NULL) {
		node* delNode = current;
		current = current->nextNode;
		delete delNode;
	}
}

void LinkedList::addNode(int data) {
	//Append into the list
	if (head == NULL) {
		//Empty list
		head = new node;
		head->data = data;
		tail = head;
		size++;
		return;
	}

	//Create another node
	node* temp = new node;
	temp->data = data;
	//Move the tail of the list forward
	tail->nextNode = temp;
	tail = temp;
	//Increase the size
	size++;
}

void LinkedList::shiftZero() {
	if (head == NULL) {
		//Empty list!
		cout << "List is empty!" << endl;
		return;
	}

	cout << "0's Shifted!" << endl;
	shiftZero(head);
}

void LinkedList::shiftZero(node*& curNode) {
	if (curNode == NULL) {
		//End condition
		return;
	}

	//Use double pointer technique to dynamically change the location of the node 
	//	without accesing its parent!

	//Traverse first
	shiftZero(curNode->nextNode);

	//Then shift
	if (curNode->data == 0) {
		//"temp" points to the memory location itself, not to the argument pointer (which is parent->nextNode) to that location
		node* temp = curNode;
		//Move the argument pointer to the next location
		curNode = curNode->nextNode;
		//Prepend the current 0 node
		temp->nextNode = head;
		head = temp;
	}

	//Will traverse back to the previous stack farm after this
}

void LinkedList::display() {
	if (head == NULL) {
		//Empty list
		cout << "Your list is empty!" << endl;
		return;
	}

	node* current = head;
	cout << "Here is your list:\n\t";
	while (current != NULL) {
		cout << current->data << " ";
		current = current->nextNode;
	}
	cout << endl;
}