CLB_CodingChallenge_6_5_2018

/*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;
}