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_v2(Node *list1, Node *list2)
{
    Node *first = new Node;
    Node *current = first;
    while(list1 != nullptr or list2 != nullptr){
        if(list1 != nullptr and list2 == nullptr){
            current -> next = list1;
            current = current -> next;
            list1 = list1 -> next;
        }
        else if(list1 == nullptr and list2 != nullptr){
            current -> next = list2;
            current = current -> next;
            list2 = list2 -> next;
        }
        else{
            if(list1 -> val < list2 -> val){
                current -> next = list1;
                current = current -> next;
                list1 = list1 -> next;
            }
            else{
                current -> next = list2;
                current = current -> next;
                list2 = list2 -> next;
            }
        }
    }
    return first -> next;
}

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_v2(list1, list2);
}