MergeSort zehu ze acol

    ListNode *merge(ListNode *leftHead, ListNode *rightHead)
    {
        ListNode dummy_head(INT_MAX);
        ListNode *tailOfSortedList = &dummy_head;
        while (leftHead && rightHead)
        {
            if (leftHead->val < rightHead->val)
            {
                tailOfSortedList->next = leftHead;
                leftHead = leftHead->next;
            }
            else
            {
                tailOfSortedList->next = rightHead;
                rightHead = rightHead->next;
            }
            tailOfSortedList = tailOfSortedList->next;
        }

        while (leftHead)
        {
            tailOfSortedList->next = leftHead;
            leftHead = leftHead->next;
            tailOfSortedList = tailOfSortedList->next;
        }

        while (rightHead)
        {
            tailOfSortedList->next = rightHead;
            rightHead = rightHead->next;
            tailOfSortedList = tailOfSortedList->next;
        }

        tailOfSortedList = dummy_head.next;
        return tailOfSortedList;
    }

    ListNode *sortList(ListNode *head)
    {
        if (!head || !(head->next))
            return head;
        ListNode *slow, *fast, *prevMiddle;
        ListNode dummy_head(INT_MAX);
        dummy_head.next = head;

        prevMiddle = &dummy_head;

        slow = fast = head;
        while (fast && fast->next)
        {
            prevMiddle = prevMiddle->next;
            slow = slow->next;
            fast = fast->next->next;
        }
        // slow = mid node of current list
        prevMiddle->next = nullptr;
        // now we reduced the list to two sublists: head until prevMiddle and slow until the tail of the current list.
        ListNode *left = sortList(head);
        ListNode *right = sortList(slow);

        ListNode *sortedList = merge(left, right);

        return sortedList;
    }