#include <iostream>

using namespace std;

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

// Print using standard notation
ostream& operator << (ostream& outStream, const Node* n);

// Insert a node* at a given position
Node* insert(Node* head, int pos, Node* toInsert);

// Remove all Nodes with a given value
Node* removeVal(Node* head, int valToDelete);


// Allocate a new node and add it to the end of the list
Node* addToEnd(Node* head, int valToAdd);

int main()
{
  Node a;
  Node b;
  Node c;
  Node* head = &a;

  a.val = 3;
  b.val = 8;
  c.val = 10;

  a.next = &b;
  b.next = NULL;
  c.next = NULL;

  // Should be 3 8
  cout << head << endl;
  
  // After this op, should be 3 8 10
  head = insert(head, 2, &c);
  cout << head << endl;

  // After this op, should be 3 8 10 10
  head = addToEnd(head, 10);
  cout << head << endl;

  // After this op, should be 3 8
  head = removeVal(head, 10);
  cout << head << endl;

  // Remove the 8
  head = removeVal(head, 8);

  // Make the list 3 3 3 3 4
  head = addToEnd(head, 3);
  head = addToEnd(head, 3);
  head = addToEnd(head, 3);
  head = addToEnd(head, 4);

  // Remove leading 3s to check that removal works well
  head = removeVal(head, 3);

  // Should be 4
  cout << head << endl;
}


ostream& operator << (ostream& outStream, const Node* n)
{
   // We do this in a slightly odd way so the spaces get printed correctly.
  if (n != NULL)
    {
      outStream << n->val;
      n = n->next;
    }

  while (n != NULL)
    {
      // Print each value
      outStream << " " << n->val;

      // Move through the list
      n = n->next;
    }
  
  return outStream;
}

Node* insert(Node* head, int pos, Node* toInsert)
{
  if (pos == 0)
    {
      toInsert->next = head;
      return toInsert;
    }

  Node* cur = head;
  while (pos > 1)
    {
      cur = cur->next;
      pos--;
    }
  
  toInsert->next = cur->next;
  cur->next = toInsert;

  return head;

}

// A beautiful recursive solution to removing all of a given value
// from a list.  The iterative solution is about 10-15 lines.
Node* removeVal(Node* head, int valToDelete)
{
  if (head == NULL) return NULL;
  if (head->val == valToDelete) return removeVal(head->next, valToDelete);
  head->next = removeVal(head->next, valToDelete);
  return head;
}

Node* addToEnd(Node* head, int valToAdd)
{
  if (head == NULL) 
    {
      Node* t = new Node;
      t->val = valToAdd;
      t->next = NULL;
      return t;
    }
  head->next = addToEnd(head->next, valToAdd);
  return head;
}