#include <stdio.h>

struct node
{
    int val;
    struct node *pNext;
};


struct node *gen()
{
    struct node *pHead = NULL;

    for(int i = 10; i > 0; i--){
        struct node * p = malloc(sizeof(struct node));
        p -> val = i;
        p -> pNext = pHead;
        pHead = p;
    }   
    return pHead;
}

void display(struct node *pHead) 
{
    while( pHead != NULL)
    {   
        printf("%d ", pHead->val);
        pHead = pHead->pNext;
    }   
    printf("\n");
}

struct node * reverse(struct node *pHead)
{
    if (pHead == NULL || pHead -> pNext == NULL)
    {   
        return pHead;
    }   
    struct node *p = pHead -> pNext;
    struct node *pNewHead =  reverse(p);
    p -> pNext = pHead;
    pHead ->pNext = NULL;
    return pNewHead;
}
struct node * merge(struct node *pHeadA, struct node *pHeadB)
{
    if(pHeadA == NULL )
        return pHeadB;
    if(pHeadB == NULL )
        return pHeadA;
    if(pHeadA -> val < pHeadB -> val)
    {
        pHeadA -> pNext = merge(pHeadA -> pNext, pHeadB);
        return pHeadA;
    }
    else
    {
        pHeadB -> pNext = merge(pHeadA, pHeadB -> pNext);
        return pHeadB;
    }
}

int main()
{
    struct node *pHead = gen();
    display(pHead);
    struct node *pHeadB = gen();
    pHead = merge(pHead, pHeadB),
    display(pHead);
    pHead = reverse(pHead);
    display(pHead);
}