#include <stdlib.h>

#include <stdio.h>

#include <string.h>

 

typedef struct

{

    char ch;

    void * next;

} l_list;

 

l_list * genNode( char ch )

{

    l_list * rval = 0;

 

    rval = ( l_list * )malloc( sizeof( l_list ) );

    rval->ch = ch;

    rval->next = 0;

 

    return rval;

}

 

l_list * genList( const char *instr )

{

    int len = strlen( instr ), i = 0;

    l_list *rval = 0, *next = 0;

 

    if ( !len )

        return 0;

 

    next = rval = genNode( instr[0] );

 

    for (i = 1; i < len; i++ )

    {

        l_list * tmpPtr = genNode( instr[i] );

 

        next->next = tmpPtr;

        next = ( l_list * )next->next;

    }

 

    return rval;

}

 

void freeList( l_list *head )

{

    if ( !head )

        return;

 

    if ( head->next )

        freeList( ( l_list * )head->next );

 

    free( head );

}

 

int getListLen( l_list *head )

{

    static int c = 0;

 

    if ( !head )

        return 0;

 

    c++;

 

    if ( head->next )

        getListLen( ( l_list * )head->next );

 

    return c;

}

 

char * genStr( char * buf, l_list *head )

{

    if ( !head || !buf )

        return 0;

 

    *buf = head->ch;

 

    if ( head->next )

        genStr( buf + 1, ( l_list * )head->next );

    else

        *( buf + 1 ) = 0;

 

    return buf;

}

 

l_list * getPreTail( l_list *head )

{

    if ( !head )

        return 0;

 

    if ( !head->next )

        return head;

 

    if ( ( ( l_list * )head->next)->next )

        return getPreTail( ( l_list * )head->next );

 

    return head;

}

 

int main()

{

    l_list * llHead;

    char * str = "Hi there", *outStr;

 

    llHead = genList( str );

    outStr = ( char * )malloc( getListLen( llHead ) + 1 );

 

    while ( llHead )

    {

        l_list *preTail = getPreTail( llHead ), *tail;

 

        if ( preTail && ( tail = ( l_list * )preTail->next ) )

        {

            preTail->next = 0;

            tail->next = llHead;

            llHead = tail;

        }

 

        genStr( outStr, llHead );

        printf( "%s\n", outStr );

        system( "pause" );

    }

 

    freeList( llHead );

    free( outStr );

    system( "pause" );

    

    return 0;

}