#include <iostream>

using namespace std;

class Node
{
public:
  int val;
  Node* next;
};

////////////////////////////////////////////////
// Predeclarations
void printList(Node* head);
unsigned int size(Node* head);
Node* insert(Node* head, int pos, int toInsert);
Node* removeVal(Node* head, int valToDelete);
Node* addToEnd(Node* head, int valToAdd);

int main()
{
  // Allocate three nodes on the heap.  Remember that the heap means
  // using "new"
  Node* a = new Node;
  Node* b = new Node;
  Node* c = new Node;
  
  // Set the values
  a->val = 3;
  b->val = 8;
  c->val = 10;
  
  // Set the pointers
  a->next = b;
  // These pointers probably are already NULL, but being explicit doesn't
  // hurt.
  b->next = NULL;
  c->next = NULL;

  // Now we do testing.  Begin with just testing printList.
  cout << "Printing a, should print 3 8" << endl;
  printList(a);
  cout << endl;
    
  // Test insertion at the tail
  cout << "Inserting 15 at tail, should print 3 8 15" << endl;
  a = insert(a, 2, 15);
  printList(a);
  cout << endl;

  // Test insertion at the head
  cout << "Inserting 15 at the head, should print 15 3 8 15" << endl;
  a = insert(a, 0, 15);
  printList(a);
  cout << endl;

  // Test removing a middle value
  cout << "Removing value 8, should print 15 3 15" << endl;
  a = removeVal(a, 8);
  printList(a);
  cout << endl;

  // Test removing head and tail values
  cout << "Removing value 15, should print 3" << endl;
  a = removeVal(a, 15);
  printList(a);
  cout << endl;

  // Test the addToEnd function
  cout << "Adding to end value 20, should print 3 20" << endl;
  a = addToEnd(a, 20);
  printList(a);
  cout << endl;

}

void printList(Node* head)
{
  // Doing this recursively, because I'm lazy.  The simple case: the list
  // is empty.
  if (head == NULL) return;

  // If the list wasn't empty, print out the first element.
  cout << head->val << " ";

  // Print out the rest of the list.  Since the rest of the list is
  // smaller than all of the list, this moves us closer to the base-case,
  // and thus the recursion will be successful.
  printList(head->next);
}

unsigned int size(Node* head)
{
  int counter = 0;

  // Not recursive this time, just to show how a simple loop works
  while (head != NULL)
    {
      // It is good practice to use pre-increment instead of post-increment
      // whenever possible.
      ++counter;
      
      // Advance to the next Node.  If this is the end of the list, the 
      // value will be NULL and the loop will terminate
      head = head->next;
    }

  // Return the number of nodes that we found
  return counter;
}

Node* insert(Node* head, int pos, int toInsert)
{
  // Base case #1: we want to insert at the head of the list
  if (pos == 0)
    {
      // Create a new node
      Node* newNode = new Node;
      newNode->val = toInsert;

      // Make it point to the old head of the list
      newNode->next = head;

      // Return it as the new head of the list
      return newNode;
    }

  // If the list is empty, just return the empty list (this means that
  // the insertion failed.  Later on we'll cover exceptions and this
  // would be a good place to throw an exception.)
  if (head == NULL) return head;

  // The only tricky part: insert the value somewhere in the rest of the list.
  head->next = insert(head->next, pos - 1, toInsert);
  
  return head;
}

Node* removeVal(Node* head, int valToDelete)
{
  // Base case 1: the list is empty, we are done
  if (head == NULL) return NULL;

  // If we need to remove the value, remove it
  if (head->val == valToDelete)
    {
      Node* temp = head->next;
      delete head;
      return removeVal(temp, valToDelete);
    }
  
  // Otherwise, remove the value from the rest of the list
  head->next = removeVal(head->next, valToDelete);
  
  return head;
}

// If we already have insert working, this is fairly simple. 
// Not the most efficient code that we could write (it makes 2 
// passes through the list), but still O(n).
Node* addToEnd(Node* head, int valToAdd)
{
  return insert(head, size(head), valToAdd);
}