A classificação de uma lista vinculada pode ser feita usando vários algoritmos; uma abordagem comum é usar a classificação por mesclagem. A classificação por mesclagem segue uma estratégia de dividir para conquistar:
1.
Divida a lista: - Se a lista contiver um ou zero nós, ela será considerada já ordenada.
- Caso contrário, divida a lista em duas metades aproximadamente iguais.
2.
Conquistar (classificar as sublistas): - Aplicar recursivamente o algoritmo de classificação por mesclagem a ambas as metades da lista, classificando-as efetivamente.
3.
Mesclar as sublistas classificadas: - Comece com dois ponteiros, um apontando para o início de cada sublista classificada.
- Compare os dados nos nós apontados por esses ponteiros para determinar qual elemento vem primeiro na ordem de classificação.
- Anexe o elemento menor a uma nova lista que está sendo construída.
- Mova o ponteiro correspondente para o próximo nó da sublista.
4.
Repita a etapa 3: - Continue comparando e mesclando elementos de ambas as sublistas, movendo os ponteiros conforme necessário.
- Repita este processo até que todos os elementos de ambas as sublistas tenham sido mesclados na nova lista.
5.
Retorne a lista ordenada mesclada: - Depois que todos os elementos forem mesclados, a nova lista resultante representa a lista vinculada classificada. Retorne esta lista classificada como resposta final.
Ao dividir sistematicamente a lista em partes menores, classificá-las e mesclá-las novamente, a classificação por mesclagem classifica efetivamente toda a lista vinculada em ordem crescente. A complexidade de tempo desta abordagem é O(n log n), onde n é o número de nós na lista vinculada.
