Merge Sort for Linked List

PROBLEM :

Given Pointer/Reference to the head of a linked list, task is to Sort the given linked list using Merge Sort.

You need to complete the function splitList() and mergeList(), which will be called by the function mergeSort().

void mergeSort(struct node** headRef)
{
    struct node* head = *headRef;
    struct node* a, b;
    if ((head == NULL) || (head->next == NULL))
       return NULL;
    splitList(head, &a, &b);
    mergeSort(&a);
    mergeSort(&b);
    *headRef = mergeList(a, b);
}

The spliList() function takes three input, head of the linked list and references to two pointers that are initially null. The function changes these pointers so that will point to the two new splitted lists, left and right halves respectively. The function splits the linked list in to two halves just like in standard merge sort and store the two new head in pointer a and b respectively. As the name suggests function mergeList will merge two linked lists, as in standard merge sort and should head pointer to of the new merged list.

Note: If the length of linked list is odd, then the extra node should go in the first list while splitting.

Input:
There will be multiple test cases, for each test case function mergeSort() will be called separately. The only input to the function is the pointer/reference to the head of the linked list.

Output:
For each test, print the sorted linked list.

Constraints:
1<=T<=100
1<=N<=105

Example:
Input:
2
5
3 5 2 4 1
3
9 15 0

Ouput:
1 2 3 4 5
0 9 15

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

/* Structure of the linked list node is as
struct node
{
int data;
struct node* next;
};
*/
/* split the nodes of the given list into front and back halves,
     and return the two lists using the reference parameters.*/
void splitList(struct node* source, struct node** frontRef, struct node** backRef)
{
    if(source==NULL) return ;
   
    node *slow,*fast ;
    slow=source ;
    fast=source->next ;
   
    while(fast&&fast->next)
    {
        slow=slow->next ;
        fast=fast->next->next ;
    }
   
    (*frontRef)=source ;
    (*backRef)=slow->next ;
    slow->next=NULL ;
}

// merges two sorted list into one big list
struct node* mergeList(struct node* a, struct node* b)
{
    if(!a&&!b)
        return NULL ;
    if(!a)
        return b ;
    if(!b)
        return a ;
       
    node *final ;
    if(a->data<b->data)
    {
        final=a ;
        final->next=mergeList(a->next,b) ;
    }
    else
    {
        final=b ;
        final->next=mergeList(a,b->next) ;
    }
    return final ;
}

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