Merge Sort for Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
int _len(ListNode* head){
    int ans=0;
    while(head){head=head->next; ans++;}
    return ans;
}
ListNode* find_mid(ListNode *head){
    int half=_len(head)/2; if(half>0)half--;  //reducing half by one so it send just before the middle
    ListNode *mid=head;                       //node
    while(half--){
        mid=mid->next;
    }
    return mid;
}
ListNode *merge(ListNode *head,ListNode *mid){

    if(!head) return mid;
    if(!mid) return head;
    ListNode *root;
    if(head->val<mid->val){ root=new ListNode(head->val);head=head->next;}
    else{ root=new ListNode(mid->val);mid=mid->next;}
    ListNode *cur=root;
    while(head && mid){
        if(head->val<mid->val){ cur->next=new ListNode(head->val);cur=cur->next; head=head->next;}
        else{ cur->next=new ListNode(mid->val);cur=cur->next;mid=mid->next;}
    }
    while(head){
        cur->next=new ListNode(head->val);cur=cur->next;head=head->next;
    }
    while(mid){
        cur->next=new ListNode(mid->val);cur=cur->next;mid=mid->next;
    }
    return root;
}
ListNode* mergesort(ListNode* head){
    if(!(head->next)) return head;  //If only one node,return the node
    ListNode *temp=find_mid(head);  //temp is having node just before mid node so that we can break
    ListNode *mid=temp->next;  //mid node
    temp->next=NULL;  //breaking the linked list into two halves(one might be bigger in odd case)
    head=mergesort(head);
    mid=mergesort(mid);
    ListNode *ans=merge(head,mid);

    return ans;
}
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return head;
        return mergesort(head);
    }
};