Seja uma lista encadeada cujos registros possuam informação do tipo inteiro. Escreva um programa que ordena a lista em ordem crescente em relação à informação.

Passo 1

O enunciado pede para ordenar uma lista simplesmente encadeada de inteiros em ordem crescente. O conteúdo da matéria aqui é algoritmos de ordenação em listas ligadas, e vamos usar o merge sort, pois ele tem complexidade O(n log n) e se adapta bem a ponteiros.

Passo 2

Precisamos de uma função para dividir a lista em duas metades. Usamos o método de ponteiros lento (slow) e rápido (fast). O ponteiro fast anda dois nós por vez e o slow anda um, assim quando fast chega ao fim, slow está no meio. Separamos a lista em head → slow e slow→next → tail.

Passo 3

Depois de dividir, precisamos de uma função que mescle duas sublistas ordenadas. Essa função compara recursivamente os valores dos nós das duas listas e vai ligando o menor como próximo de um ponteiro result, construindo a lista ordenada final.

Passo 4

A função principal mergeSort é recursiva: se a lista tiver 0 ou 1 elemento, já está ordenada (caso base). Senão, dividimos em duas metades, chamamos mergeSort recursivamente em cada metade e depois usamos sortedMerge para juntar as duas partes ordenadas.

Passo 5

Basta chamar mergeSort passando o ponteiro para o head da lista. A função retorna um novo ponteiro head para a lista completamente ordenada.

Resposta

#include <stdio.h>
#include <stdlib.h>
// Definição do nó da lista
typedef struct Node {
int data;
struct Node* next;
} Node;
// Função que mescla duas listas ordenadas
Node* sortedMerge(Node* a, Node* b) {
if (!a) return b;
if (!b) return a;
Node* result = NULL;
if (a->data <= b->data) {
result = a;
result->next = sortedMerge(a->next, b);
} else {
result = b;
result->next = sortedMerge(a, b->next);
}
return result;
}
// Função que divide a lista em duas metades
void frontBackSplit(Node* source, Node** frontRef, Node** backRef) {
Node* slow = source;
Node* fast = source->next;
while (fast) {
fast = fast->next;
if (fast) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
// Algoritmo mergeSort para listas ligadas
void mergeSort(Node** headRef) {
Node* head = *headRef;
if (!head || !head->next) return; // caso base
Node* a;
Node* b;
frontBackSplit(head, &a, &b);

mergeSort(&a);
mergeSort(&b);

*headRef = sortedMerge(a, b);
}
// Função auxiliar para inserir um novo nó no início
void push(Node** headRef, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = *headRef;
*headRef = newNode;
}
// Função auxiliar para imprimir a lista
void printList(Node* node) {
while (node) {
printf("%d “, node->data);
node = node->next;
}
printf(”\n");
}
int main() {
Node* head = NULL;
// Exemplo de uso: montar a lista 15->10->5->20->3->2
push(&head, 2);
push(&head, 3);
push(&head, 20);
push(&head, 5);
push(&head, 10);
push(&head, 15);

printf("Lista original:\n");
printList(head);

mergeSort(&head);

printf("Lista ordenada:\n");
printList(head);

return 0;
}

Exercícios relacionados