Para ordenar uma lista encadeada com complexidade de tempo O(n log n) e espaço constante, utilize o algoritmo merge sort.

Análise: A exigência de O(n log n) exclui o quicksort, que no pior caso atinge O(n^2). O merge sort mantém a complexidade desejada e é adequado para listas encadeadas.

O processo consiste em:

1. Encontrar o nó intermediário usendo ponteiros rápido e lento. O rápido avança dois nós por iteração, o lento avança um nó. Quando o rápido alcançar o final, o lento estará no meio.
2. Recursivamente ordenar a primeira metade (do início até o nó anterior ao intermediário) e a segunda metade (do intermediário ao final).
3. Mesclar as sublistas ordenadas, comparando valores dos nós e apontando para o menor, até que uma lista se esgote, adicionendo então os nós restantes.

Exemplo em C++

struct NoLista {
    int valor;
    NoLista* proximo;
    NoLista(int v) : valor(v), proximo(nullptr) {}
};

class Solucao {
public:
    NoLista* ordenarLista(NoLista* cabeca) {
        if (!cabeca || !cabeca->proximo) return cabeca;
        return mergeSort(cabeca);
    }

private:
    NoLista* mergeSort(NoLista* cabeca) {
        if (!cabeca || !cabeca->proximo) return cabeca;

        NoLista* lento = cabeca;
        NoLista* rapido = cabeca->proximo;
        NoLista* anterior = nullptr;

        while (rapido && rapido->proximo) {
            anterior = lento;
            lento = lento->proximo;
            rapido = rapido->proximo->proximo;
        }

        if (anterior) anterior->proximo = nullptr;

        NoLista* esquerda = mergeSort(cabeca);
        NoLista* direita = mergeSort(lento);

        return mesclar(esquerda, direita);
    }

    NoLista* mesclar(NoLista* a, NoLista* b) {
        NoLista sentinela(0);
        NoLista* corrente = &sentinela;

        while (a && b) {
            if (a->valor <= b->valor) {
                corrente->proximo = a;
                a = a->proximo;
            } else {
                corrente->proximo = b;
                b = b->proximo;
            }
            corrente = corrente->proximo;
        }

        corrente->proximo = a ? a : b;
        return sentinela.proximo;
    }
};

Exemplo em Python

class NoLista:
    def __init__(self, valor):
        self.valor = valor
        self.proximo = None

class Solucao:
    def ordenar_lista(self, cabeca):
        if not cabeca or not cabeca.proximo:
            return cabeca
        return self._merge_sort(cabeca)

    def _merge_sort(self, cabeca):
        if not cabeca or not cabeca.proximo:
            return cabeca

        lento = cabeca
        rapido = cabeca.proximo
        anterior = None

        while rapido and rapido.proximo:
            anterior = lento
            lento = lento.proximo
            rapido = rapido.proximo.proximo

        if anterior:
            anterior.proximo = None

        esquerda = self._merge_sort(cabeca)
        direita = self._merge_sort(lento)

        return self._mesclar(esquerda, direita)

    def _mesclar(self, a, b):
        sentinela = NoLista(0)
        corrente = sentinela

        while a and b:
            if a.valor <= b.valor:
                corrente.proximo = a
                a = a.proximo
            else:
                corrente.proximo = b
                b = b.proximo
            corrente = corrente.proximo

        corrente.proximo = a if a else b
        return sentinela.proximo