Lista vinculada e ordenada em C++

#include <iostream>
#include <cstdio>
using namespace std;

/* um nó da lista unicamente ligada */
struct Node
{
    int data;
    struct Node *next;
};

/* Uma função de utilidade para inserir um nó no início da lista vinculada */
void push(struct Node** head_ref, int new_data)
{
    /* alocar o nó */
    struct Node* new_node = new Node;

    /* coloque os dados  */
    new_node->data  = new_data;

    /* vincule a lista antiga do novo nó */
    new_node->next = (*head_ref);

    /* mova a cabeça para apontar para o novo nó */
    (*head_ref)    = new_node;
}

/* Uma função de utilidade para imprimir lista vinculada */
void printList(struct Node *node)
{
    while (node != NULL)
    {
        printf("%d  ", node->data);
        node = node->next;
    }
    printf("\n");
}

//Retorna o último nó da lista
struct Node *getTail(struct Node *cur)
{
    while (cur != NULL && cur->next != NULL)
        cur = cur->next;
    return cur;
}

//Particiona a lista tomando o último elemento como o pivô
struct Node *partition(struct Node *head, struct Node *end,
                       struct Node **newHead, struct Node **newEnd)
{
    struct Node *pivot = end;
    struct Node *prev = NULL, *cur = head, *tail = pivot;

    //Durante a partição, tanto a cabeça como o final da lista podem mudar
    //que é atualizado nas variáveis newHead e newEnd
    while (cur != pivot)
    {
        if (cur->data < pivot->data)
        {
            // Primeiro nó que tem um valor menor que o pivô - torna-se
            // a nova cabeça
            if ((*newHead) == NULL)
                (*newHead) = cur;

            prev = cur;
            cur = cur->next;
        }
        else // Se o nó cur for maior do que o pivô
        {
            // Mova o nó cur para a próxima cauda e troque a cauda
            if (prev)
                prev->next = cur->next;
            struct Node *tmp = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }

    // Se os dados de pivô forem o elemento mais pequeno da lista atual,
    // pivô torna-se a cabeça
    if ((*newHead) == NULL)
        (*newHead) = pivot;

    //Atualize newEnd para o último nó atual
    (*newEnd) = tail;

    //Retornar o nó pivô
    return pivot;
}


//aqui a classificação acontece sem o nó final
struct Node *quickSortRecur(struct Node *head, struct Node *end)
{
    // base condition
    if (!head || head == end)
        return head;

    Node *newHead = NULL, *newEnd = NULL;

    // Participar na lista, newHead e newEnd serão atualizados
    // pela função de partição
    struct Node *pivot = partition(head, end, &newHead, &newEnd);

    //Se o pivô é o elemento mais pequeno - não há necessidade de recorrer
    //a parte esquerda.
    if (newHead != pivot)
    {
        //Defina o nó antes do nó pivô como NULL
        struct Node *tmp = newHead;
        while (tmp->next != pivot)
            tmp = tmp->next;
        tmp->next = NULL;

        //Recorrer para a lista antes do pivô
        newHead = quickSortRecur(newHead, tmp);

        //Mude o próximo último nó da metade esquerda para girar
        tmp = getTail(newHead);
        tmp->next =  pivot;
    }

    //Recorrer para a lista após o elemento de pivô
    pivot->next = quickSortRecur(pivot->next, newEnd);

    return newHead;
}

//A principal função para quicksort. Este é um invólucro sobre recursivo
// funcão quickSortRecur()
void quickSort(struct Node **headRef)
{
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef));
    return;
}

int main()
{
    struct Node *a = NULL;
    push(&a, 5);
    push(&a, 20);
    push(&a, 4);
    push(&a, 3);
    push(&a, 30);

    cout << "\nLista vinculada antes de ordenar \n";
    printList(a);

    quickSort(&a);

    cout << "\n\nLista vinculada apos a classificacao \n";
    printList(a);

    return 0;
}