ListNode* mergeLL(ListNode* h1,ListNode *h2){

    ListNode *head=NULL,*p=h1,*q=h2,*curr=NULL;
    while(p!=NULL && q!=NULL){
        if(p->data <q->data){
            if(head==NULL){
                head=new ListNode(p->data);
                curr=head;
            }else{
                curr->next=new ListNode(p->data);
                curr=curr->next;
            }
            p=p->next;
        }else{
            if(head==NULL){
                head=new ListNode(q->data);
                curr=head;
            }else{
                curr->next=new ListNode(q->data);
                curr=curr->next;
            }
            q=q->next;
        }
    }

    while(p != NULL){
        curr->next=new ListNode(p->data);
        curr=curr->next;
        p=p->next;
    }

    while(q != NULL){
        curr->next=new ListNode(q->data);
        curr=curr->next;
        q=q->next;
    }
    return head;
}

ListNode* mergeSort(ListNode* head) {

    if(head==NULL || head->next == NULL)
        return head;

    ListNode *slow=head,*fast=head;
    while(fast->next != NULL && fast->next->next != NULL){
        slow=slow->next;
        fast=fast->next->next;
    }

    ListNode *temp=slow;
    slow=slow->next;
    temp->next = NULL;

    ListNode *h1=mergeSort(head);
    ListNode *h2=mergeSort(slow);
    head= mergeLL(h1,h2);

    return head;
}