#include <stdio.h>
#include <malloc.h>
#include <conio.h>

//define a node
typedef struct node{
    int val;
    struct node *next;
} node;

//create a link list by tail inserting
void tail_insert(node **h,int i){
    if (*h == 0){
        *h = (node*)malloc(sizeof(node));
        (*h)->val = i;
        (*h)->next = 0;
        return;
    }
    node *p = (node*)malloc(sizeof(node)),*pl = *h;
    p->val = i;
    p->next = 0;    
    while (pl->next)
        pl = pl->next;
    pl->next = p;
    return;
}

//create a link list by head inserting
void head_insert(node **h,int i){
    if (*h == 0){
        *h = (node*)malloc(sizeof(node));
        (*h)->next = 0;
        (*h)->val = i;
        return;
    }
    node *p = (node*)malloc(sizeof(node));
    p->val = i;
    p->next = *h;
    *h = p;
    return;
}

//reverse a link list by iteration
node* reverse_iteration(node *h){
    node *nh = h,*p = 0;
    h = h->next;
    nh->next = 0;
    while (h){
        p = h;
        h = h->next;
        p->next = nh;
        nh = p;
    }
    return nh;
}

//reverse a link list by recursion
node * reverse_recursion(node *h){
    if (!h || !h->next)
        return h;
    node *p = h->next,*r = 0;
    r = reverse_recursion(p);
    p->next = h;
    h->next = 0;
    return r;
}