#include <cstdlib>
 
#include <iostream>
#include <algorithm>
#include <string>
 
template < typename T >
struct Node {
    
    T data;
    Node * next;
    
    Node( T const & data )
    : data( data ), next( 0 ) { }
    
    ~Node() {
        delete next;
    }
};
 
template < typename T >
struct LinkedList {
    
    Node<T> * head;
    size_t size;
    
    // inner class
    struct Wrapper {
        
        bool (*callee)( T const &, T const & );
        
        Wrapper( bool (*callee)(T const &, T const &) ) 
        : callee( callee ) { }
        
        bool operator()( Node<T> const * lhs, Node<T> const * rhs ) {
            return (*callee)( lhs->data, rhs->data );
        }
    };
    
    LinkedList() 
    : head( 0 ), size( 0 ) { }
    
    ~LinkedList() {
        delete head;
    }
    
    void add( Node<T> * elem ) {
        elem->next = head;
        head = elem;
        ++size;
    }
    
    void sort( bool (*cmp)(T const &, T const &) ) {
        
        Node<T> ** nodes = new Node<T>*[ size ];
        size_t idx = 0;
        for( Node<T> * curr = head; curr != 0; curr = curr->next ) {
            nodes[ idx++ ] = curr;
        }
        
        std::sort( nodes, nodes+size, Wrapper(cmp) );
        head = nodes[ 0 ];
        for( idx = 1; idx != size; ++idx ) {
            nodes[ idx-1 ]->next = nodes[ idx ];
        }
        nodes[ size-1 ]->next = 0;
        delete [] nodes;
    }
};
 
bool userDefinedComparator( std::string const & lhs,
                            std::string const & rhs ) {
    return rhs < lhs;                                
}
 
int main() {
    
    using namespace std;
    
    LinkedList<string> ll;    
    ll.add( new Node<string>("world") );
    ll.add( new Node<string>("the") );
    ll.add( new Node<string>("hello") );
    
    for( Node<string> * curr = ll.head; curr != 0; curr = curr->next ) {
        cout << curr->data << " ";
    }
    cout << endl;
    
    ll.sort( &userDefinedComparator );
    
    for( Node<string> * curr = ll.head; curr != 0; curr = curr->next ) {
        cout << curr->data << " ";
    }
    cout << endl;
}