Ordenar uma lista simplesmente ligada de forma eficiente requer algoritmos que minimizem o acesso aleatório, priorizando o acesso sequencial. A seguir, exploramos as abordagens de Merge Sort (Top-down e Bottom-up) e o uso de Filas de Prioridade.

1. Merge Sort Top-down (Recursivo)

Esta abordagem utiliza a estratégia de "dividir para conquistar". O processo consiste em encontrar o meio da lista usando a técnica de ponteiros rápido e lento (fast/slow pointers), dividir a lista em duas metades e ordená-las recursivamente antes de entercalá-las.

/**
 * Definição para lista ligada simples.
 * public class NoLista {
 *     int valor;
 *     NoLista proximo;
 *     NoLista(int x) { valor = x; }
 * }
 */
class SolucaoMergeSortTopDown {
    public NoLista sortList(NoLista inicio) {
        if (inicio == null || inicio.proximo == null) {
            return inicio;
        }

        // Encontrar o ponto médio
        NoLista anterior = null, lento = inicio, rápido = inicio;
        while (rápido != null && rápido.proximo != null) {
            anterior = lento;
            lento = lento.proximo;
            rápido = rápido.proximo.proximo;
        }

        // Desconectar as duas metades
        anterior.proximo = null;

        NoLista l1 = sortList(inicio);
        NoLista l2 = sortList(lento);

        return intercalar(l1, l2);
    }

    private NoLista intercalar(NoLista a, NoLista b) {
        NoLista auxiliar = new NoLista(0);
        NoLista atual = auxiliar;

        while (a != null && b != null) {
            if (a.valor < b.valor) {
                atual.proximo = a;
                a = a.proximo;
            } else {
                atual.proximo = b;
                b = b.proximo;
            }
            atual = atual.proximo;
        }

        if (a != null) atual.proximo = a;
        if (b != null) atual.proximo = b;

        return auxiliar.proximo;
    }
}

2. Merge Sort Bottom-up (Iterativo)

Diferente da versão recursiva, esta técnica elimina o overhead da pilha de chamadas, garantindo complexidade de espaço O(1). O algoritmo itera sobre a lista em tamanhos de subgruppos crescentes (1, 2, 4, 8...), fundindo segmentos adjacentes.

class SolucaoMergeSortBottomUp {
    public NoLista sortList(NoLista head) {
        if (head == null || head.proximo == null) return head;

        int total = 0;
        NoLista temp = head;
        while (temp != null) {
            total++;
            temp = temp.proximo;
        }

        NoLista dummy = new NoLista(0);
        dummy.proximo = head;

        for (int tam = 1; tam < total; tam <<= 1) {
            NoLista anterior = dummy;
            NoLista atual = dummy.proximo;

            while (atual != null) {
                NoLista esq = atual;
                NoLista dir = dividir(esq, tam);
                atual = dividir(dir, tam);
                anterior.proximo = fundir(esq, dir);
                while (anterior.proximo != null) {
                    anterior = anterior.proximo;
                }
            }
        }
        return dummy.proximo;
    }

    private NoLista dividir(NoLista inicio, int passo) {
        for (int i = 1; inicio != null && i < passo; i++) {
            inicio = inicio.proximo;
        }
        if (inicio == null) return null;
        NoLista resto = inicio.proximo;
        inicio.proximo = null;
        return resto;
    }

    private NoLista fundir(NoLista l1, NoLista l2) {
        NoLista fake = new NoLista(0);
        NoLista p = fake;
        while (l1 != null && l2 != null) {
            if (l1.valor < l2.valor) {
                p.proximo = l1;
                l1 = l1.proximo;
            } else {
                p.proximo = l2;
                l2 = l2.proximo;
            }
            p = p.proximo;
        }
        p.proximo = (l1 != null) ? l1 : l2;
        return fake.proximo;
    }
}

3. Ordenação com Fila de Prioridade (Min-Heap)

Esta abordagem utiliza uma estrutura de dados de Heap para gerenciar os nós. Embora simples de implementar, a complexidade de espaço aumenta para O(n) devido ao armazenamento de todos os nós na fila.

import java.util.PriorityQueue;

class SolucaoPriorityQueue {
    public NoLista sortList(NoLista head) {
        if (head == null) return null;

        // Fila de prioridade comparando os valores dos nós
        PriorityQueue<NoLista> heap = new PriorityQueue<>((n1, n2) -> n1.valor - n2.valor);

        NoLista marcador = head;
        while (marcador != null) {
            heap.offer(marcador);
            marcador = marcador.proximo;
        }

        NoLista sentinela = new NoLista(0);
        NoLista rastro = sentinela;

        while (!heap.isEmpty()) {
            NoLista menor = heap.poll();
            rastro.proximo = menor;
            rastro = rastro.proximo;
            // Importante limpar o ponteiro para evitar ciclos
            rastro.proximo = null;
        }

        return sentinela.proximo;
    }
}

A escolha entre estes métodos depende das restrições de memória: o Merge Sort Bottom-up é ideal quando o espaço é limitado, enquanto a Fila de Prioridade oferece uma implementação mais direta e legível.