Сортировка слиянием для связанного списка

Проблема в том, что узел, который возвращает findMiddle, становится хвостовым узлом левого раздела. Это делает левый раздел всегда длиннее правого. Это настоящая проблема, когда вы начинаете со списка, состоящего всего из двух узлов, поскольку тогда левый раздел получит оба этих узла, а правый раздел не получит ни одного из них. Следовательно, рекурсия в левом разделе будет в том же состоянии, что и вы, т. е. список с двумя узлами не будет разделен на левый раздел меньшего размера.

Возьмем, к примеру, связанный список 1 → 2. Вызов findMiddle со ссылкой на 1 вернет ссылку на узел 2. sortList сделает этот узел хвостом левого раздела, установив следующий указатель этого узла на nullptr -- который был уже nullptr, поэтому ничего не изменится. Таким образом, левый раздел тоже 1 → 2, и теперь вы видите, что не добились никакого прогресса: вы заперты в бесконечной рекурсии.

Чтобы решить эту проблему, убедитесь, что если findMiddle вызывается в списке с четным числом узлов, он возвращает ссылку на узел, который находится в конце первой половины. Таким образом, в случае 1 → 2 он должен возвращать ссылку на узел 1, а не на узел 2.

Чтобы это произошло, измените эту инициализацию:

    ListNode *fast=head;

на этот:

    ListNode *fast=head->next;

С этим изменением все должно работать так, как задумано.

Поскольку Trincot уже предоставил ответ, итеративная сортировка слиянием снизу вверх более эффективна, поскольку позволяет избежать сканирования списков для их разделения.

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

typedef struct NODE_{                       /* base node struct */
    struct NODE_ * next;
    int            data;
}NODE;

NODE * Merge(NODE *pNode0, NODE *pNode1)
{
NODE *pMrg;
NODE **ppMrg = &pMrg;
    if (pNode0 == NULL)                  /* if either list empty, */
        return pNode1;                  /*  return the other */
    if (pNode1 == NULL)
        return pNode0;
    while(1){                           /* merge the lists */
        if (pNode0->data <= pNode1->data){
            *ppMrg = pNode0;
            ppMrg = &(pNode0->next);
            pNode0 = *ppMrg;
            if (pNode0 == NULL){
                *ppMrg = pNode1;
                break;}}
        else{
            *ppMrg = pNode1;
            ppMrg = &(pNode1->next);
            pNode1 = *ppMrg;
            if (pNode1 == NULL){
                *ppMrg = pNode0;
                break;}}}
    return pMrg;
}


/* size of internal array */
#define ASZ 32
NODE *MergeSort(NODE * pNode)
{
NODE *apNode[ASZ] = {NULL};             /* array of lists */
NODE *pNext;
size_t i;
    if (pNode == NULL || pNode->next == NULL)
        return pNode;
    /* merge nodes into array */
    while(pNode){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; i < ASZ && apNode[i] != NULL; i++){
            pNode = Merge(apNode[i], pNode);
            apNode[i] = NULL;}
        if (i == ASZ)                    /* don't go past end array */
            i--;
        apNode[i] = pNode;
        pNode = pNext;}
    /* merge array into a single list */
    pNode = NULL;
    for(i = 0; i < ASZ; i++)
        pNode = Merge(apNode[i], pNode);
    return pNode;
}