Escreva uma função que inverte a ordem das células de uma lista encadeada (a primeira passa a ser última, segunda passa a ser penúltima etc.). Faça isso sem usar espaço auxiliar; apenas altere os ponteiros.
Passo 1
O objetivo é criar uma função que receba o ponteiro para o primeiro nó de uma lista simplesmente encadeada e retorne o ponteiro para o novo primeiro nó, com todas as ligações invertidas. Vamos usar somente manipulação de ponteiros (sem espaço auxiliar extra), aplicando técnicas básicas de listas encadeadas.
Passo 2
Precisamos primeiro ter em mente a estrutura do nó. Tipicamente definimos: struct Node { int data; struct Node *next; }; a função terá assinatura: struct Node *reverseList(struct Node *head).
Passo 3
A ideia principal é usar três ponteiros auxiliares: prev (anterior), curr (atual) e next (próximo). Inicializamos prev com NULL e curr com head. A cada iteração vamos:
— Salvar a referência ao próximo nó: next = curr->next;
— Fazer o ponteiro current->next passar a apontar para o anterior: curr->next = prev;
— Avançar prev para curr e curr para next: prev = curr; curr = next;
— Salvar a referência ao próximo nó: next = curr->next;
— Fazer o ponteiro current->next passar a apontar para o anterior: curr->next = prev;
— Avançar prev para curr e curr para next: prev = curr; curr = next;
Passo 4
Esse laço inverte o sentido dos links um a um. Quando curr ficar NULL, chegamos ao final da lista original e prev estará apontando para o novo primeiro nó.
Passo 5
Por fim, como prev agora aponta para o início da lista invertida, basta retorná-lo. A lista original não ocupa espaço extra porque reaproveitamos e invertemos todos os ponteiros existentes.
Resposta
#include <stdlib.h>
// Definição do nó
struct Node {
int data;
struct Node *next;
};
struct Node {
int data;
struct Node *next;
};
// Função que inverte a lista in-place
struct Node* reverseList(struct Node* head) {
struct Node *prev = NULL;
struct Node *curr = head;
struct Node *next = NULL;
struct Node* reverseList(struct Node* head) {
struct Node *prev = NULL;
struct Node *curr = head;
struct Node *next = NULL;
while (curr != NULL) {
next = curr->next; // armazena o próximo
curr->next = prev; // inverte o ponteiro
prev = curr; // avança prev
curr = next; // avança curr
}
return prev; // novo head da lista invertida
}