Rearrange/Reorder a given linked list in-place

PROBLEM :

Given a singly linked list L0 -> L1 -> … -> Ln-1 -> Ln. Rearrange the nodes in the list so that the new formed list is : L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 …

You are required do this in-place without altering the nodes’ values.

Examples:
Input:  1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

Input:

In this problem, method takes one argument: Address of the head of the linked list. The function should not read any input from stdin/console.
The node structure has a data part which stores the data and a next pointer which points to the next element of the linked list.
There are multiple test cases. For each test case, this method will be called individually.

Output:

Reorder it as explained above.

Constraints:

1<=T<=200
1<=N<=200

Example:

Input:

2
3
1 2 3
4
1 7 3 4

Output:

1 3 2
1 4 7 3

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

/* Following is the Linked list node structure */
/*struct node
{
    int data;
    struct node* next;
};*/



struct node* find_mid(struct node *) ;
struct node* reverse_list(struct node *) ;
struct node *merge_2list(struct node*,struct node*) ;

void reorderList(struct node* head)
{
    if(head==NULL)
        return ;
       
    struct node *temp,*list1,*list2 ;
    temp=find_mid(head) ;
   
    list2=temp->next ;
    list1=head ;
    temp->next=NULL ;
   
    list2=reverse_list(list2) ;
 
    head=merge_2list(list1,list2) ;
}

struct node* find_mid(struct node *head)
{
    struct node *t1,*t2 ;
    t1=head ;
    t2=head->next ;
   
    while(t2!=NULL&&t2->next!=NULL)
    {
        t1=t1->next ;
        t2=t2->next->next ;
    }
    return t1 ;
}

struct node* reverse_list(struct node *head)
{
    if(head==NULL)
        return head ;
       
    if(head->next==NULL)
    return head ;
   
    struct node *one ,*two ,*third ;
    one=head ;
    two=one->next ;
    third=two->next ;
   
    one->next=NULL ;
    two->next=one ;
   
    while(third!=NULL)
    {
        one=two ;
        two=third ;
        third=third->next ;
       
        two->next=NULL ;
    }
    return two ;
}



struct node *merge_2list(struct node *list1,struct node *list2)
{
    struct node *final,*temp,*ptr ;
    bool swap=true ;
    final=NULL ;
   
    if(list1==NULL)
        return list2 ;
    if(list2==NULL)
        return list1 ;
       
    while(list1!=NULL&&list2!=NULL)
    {
        temp=(struct node*)malloc(sizeof(struct node)) ;
        temp->next=NULL ;
       
        if(swap)
        {
            temp->data=list1->data ;
            list1=list1->next ;
            swap=!swap ;
        }
        else
        {
            temp->data=list2->data ;
            list2=list2->next ;
            swap=!swap ;
        }
       
        if(final==NULL)
            final=temp ;
        else
        {
            ptr=final ;
            while(ptr->next!=NULL)
                ptr=ptr->next ;
            ptr->next=temp ;
        }
    }
   
    if(list1!=NULL)
    {
        if(final==NULL)
            final=list1 ;
        else
        {
            ptr=final ;
            while(ptr->next!=NULL)
                ptr=ptr->next ;
            ptr->next=list1 ;
        }
    }
   
    if(list2!=NULL)
    {
        if(final==NULL)
            final=list2 ;
        else
        {
            ptr=final ;
            while(ptr->next!=NULL)
                ptr=ptr->next ;
            ptr->next=list2 ;
        }
    }
   
return final ;
}



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