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>
#include <stdlib.h>
// Definição do nó da lista
typedef struct Node {
int data;
struct Node* next;
} Node;
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;
}
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;
}
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
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;
}
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");
}
void printList(Node* node) {
while (node) {
printf("%d “, node->data);
node = node->next;
}
printf(”\n");
}
int main() {
Node* head = NULL;
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;
}