MergeSortList.cpp

#include<bits/stdc++.h>
using namespace std;

struct node{
    int value;
    node *next;
    node(int v, node *n):value(v),next(n){}
};
void printList(node *head);
int countToEnd(node *head);

node* takeLesser(node *&first, node *&second){
    auto takeFrom = [](node *&head){
        node * res = head;
        head = head->next;
        return res;
    };
    if(first!=NULL && second!=NULL){
        if(first->value < second->value)
            return takeFrom(first);
        return takeFrom(second);
    }
    if(first==NULL)
        return takeFrom(second);
    return takeFrom(first);
}

void mergeSortList(node *&head){
    int s = countToEnd(head)/2;
    if(s==0)
        return ;
    node *iter = head;
    int count = 0;
    while(iter!=NULL && count<s-1){
        iter = iter->next;
        count++;
    }
    node *last = iter;
    iter = iter->next;
    last->next = NULL;
    mergeSortList(head);
    mergeSortList(iter);
    node *list = takeLesser(iter,head);
    node *result = list;
    while(head != NULL || iter != NULL){
        list->next=takeLesser(iter,head);
        list=list->next;
    }
    head = result;
}

int main(){
    node *head=new node(6,new node(2,new node(4,new node(11,new node(8,new node(-2,new node(0,new node(10,NULL))))))));
    //-2,0,2,4,6,8,10,11
    cout<<"Before:"<<endl;
    printList(head);
    mergeSortList(head);
    cout<<"After:"<<endl;
    printList(head);
}
void printList(node *head){
    while(head!=NULL){
        cout<<head->value<<(head->next==NULL ? "\n":" ");
        head=head->next;
    }
}

int countToEnd(node *head){
    int result = 0; 
    while(head!=NULL){
        result++;
        head=head->next;
    }
    return result;
}