#include <iostream>
using namespace std;

template <class Object>
class LinkedList
{
  public:
    LinkedList( ) : front( NULL ) { }

    void addFront( const Object & x )
      { front = new Node( x, front ); }

    void print( ) const
    {
        for( Node *p = front; p != NULL; p = p->next )
            cout << p->data << " ";
        cout << endl;
    }

    void reverse( )
      { reverse( front ); }

  private:
    struct Node
    {
        Object data;
        Node *next;

        Node( const Object & d, Node * n )
          : next( n ), data( d ) { }
    };

    Node *front;



      // The recursive routine
      // Links from first..last of list will be reversed.
      // first will then point at original last node.
    void reverse( Node * & first )
    {
          // Base case
        if( first == NULL || first->next == NULL )
            return;

        Node *oldNext = first->next;

          // Recursive reverse from next node onwards
          // As a result, oldNext will point at the last node
          // and the next pointer in first->next will be NULL.
        reverse( oldNext );

          // Set the next pointer in first->next to point back at
          // first. Then make first's next pointer NULL.
          // Then put first at the end of the list (which is
          // the value stored in oldNext, after the recursive call).
        first->next->next = first;
        first->next = NULL;
        first = oldNext;
    }


};

int main( )
{
    LinkedList<int> L;

    for( int i = 0; i < 10; i++ )
        L.addFront( i );

    L.print( );

    L.reverse( );
    L.print( );

    return 0;
}