https://www.interviewbit.com/problems/sort-list/

InterviewBit : MergeSort on the Linked List

ListNode* merge(ListNode*A, ListNode*B){
    
        ListNode * C;
    ListNode * temp;
    int i = 0;
    while(A!=NULL && B!=NULL){
        
        if(A->val > B->val){
            
            if(i==0){
                C = B;
                temp = B;
                B = B->next;
                i = 1;
            }else{
                temp->next = B;
                temp = temp->next;
                B = B->next;
            }
            
        }else{
            
            if(i==0){
                C = A;
                temp = A;
                A = A->next;
                i = 1;
            }else{
                temp->next = A;
                temp = temp->next;
                A = A->next;
            }
            
        }
        
    }
    
    while(A!=NULL){
        temp->next = A;
        temp = temp->next;
        A = A->next;
    }
    
    while(B!=NULL){
        temp->next = B;
        temp = temp->next;
        B = B->next;
    }
            
        
    return C;
    
}

ListNode* mergeSort(ListNode* top){
    
    // If top is null or it is only node. We should not further try to seperate it.
    if(top==NULL || top->next==NULL){
        return top;
    }
    
    ListNode* oneStep = top;
    ListNode* twoStep = top->next;
    
    while(twoStep!=NULL && twoStep->next!=NULL){
        
        oneStep = oneStep->next;
        twoStep = twoStep->next->next;
        
    }
    
    ListNode* left = top;
    ListNode* right = oneStep->next;
    
    // So that left can be ended with NULL.
    oneStep->next = NULL;
    
    left = mergeSort(left);
    right = mergeSort(right);
    
    return merge(left,right);
} 

ListNode* Solution::sortList(ListNode* A) {
    return mergeSort(A);
}