void SplitList_v3(Node *list, Node *&list1, Node *&list2)
{
    Node *slow = list;
    Node *fast = list;
    while(fast -> next != nullptr and fast -> next -> next != nullptr){
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    list1 = slow -> next;
    slow -> next = nullptr;
    list2 = list;
}

Node *MergeLists_v3(Node *&list1, Node *&list2)
{
    Node *result = nullptr;
    if(list1 == nullptr)
        return list2;
    else if(list2 == nullptr)
        return list1;

    if(list1 -> val < list2 -> val){
        result = list1;
        result -> next = MergeLists_v3(list1 -> next,list2);
    }
    else{
        result = list2;
        result -> next = MergeLists_v3(list1,list2 -> next);
    }
    return result;
}

void MergeSortList(Node *&list)
{
    if(list == nullptr or list->next == nullptr) return;
    Node *list1, *list2;
    SplitList_v3(list, list1, list2);
    MergeSortList(list1);
    MergeSortList(list2);
    list = MergeLists_v3(list1, list2);
}