Linked List that is Sorted Alternatingly

PROBLEM :

Given a Linked list of size N, the list is in alternating ascending and descending orders, your task is to complete the function sort() that sorts the given linked list in non-decreasing order.

Example:
Input List: 10->40->53->30->67->12->89->NULL
Output List: 10->12->30->43->53->67->89->NULL

Input:
The function takes a single argument as input the reference pointer to the head of the linked list.
There are T test cases and for each test case the function will be called separately.

Output:
For each test case function should return reference pointer to the head of the new linked list.

Constraints:
1<=T<=100
1<=N<=100
0<=A[]<=10^3

Example:
Input:
2
6
1 9 2 8 3 7
5
13 99 21 80 50

Output:
1 2 3 7 8 9
13 21 50 80 99

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/*Structure of Node of the linked list is as
struct Node
{
int data;
struct Node *next;
};
*/
// your task is to complete this function

void AlternatSplit(Node *,Node **,Node **) ;
Node * Reverse(Node *) ;
Node * mearge(Node *,Node *) ;

void sort(Node **head)
{
    if(!(*head))
        return ;
     
    Node *head1,*head2 ;
 
    AlternatSplit(*head,&head1,&head2) ;
 
    head2=Reverse(head2) ;
 
    (*head)=mearge(head1,head2) ;
}

void AlternatSplit(Node *head,Node **head1,Node **head2)
{
    (*head1)=head ;
    (*head2)=head->next ;
 
    Node *temp,*ptr ;
    temp=head ;
    ptr=head->next ;
 
    while(ptr)
    {
        temp->next=ptr->next ;
        temp=ptr ;
        ptr=ptr->next ;
    }
    temp->next=NULL ;
}

Node * Reverse(Node *head)
{
    if(!head||!head->next)
        return head ;
     
    struct Node* one,*two,*three ;
    one=head ;
    two=one->next ;
    three=two->next ;
 
    one->next=NULL ;
    two->next=one ;
 
    while(three)
    {
        one=two ;
        two=three ;
        three=three->next ;
     
        two->next=one ;
    }
    return two ;
}

Node * mearge(Node *one,Node *two)
{
    if(!one&&!two)
        return NULL ;
     
    if(!one)
        return two ;
    if(!two)
        return one ;
     
    Node *final ;
 
    if(one->data<two->data)
    {
        final=one ;
        final->next=mearge(one->next,two) ;
    }
    else
    {
        final=two ;
        final->next=mearge(one,two->next) ;
    }
    return final ;
}

--------------------------------------------------------------------------------