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;

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;
};
// 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;
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
}

Exercícios relacionados