Crie um método não-recursivo que reverta uma lista duplamente ligada com n elementos.
Passo 1
O enunciado pede que eu crie um método não-recursivo que reverta uma lista duplamente ligada com n elementos. Em termos práticos, isso significa:
Pergunta: implementar uma rotina que receba o ponteiro para o primeiro nó (geralmente chamado de head) de uma lista duplamente ligada e retorne o ponteiro para o início da lista após ela ter sido invertida (isto é, o antigo último nó passa a ser o novo head).
Informações dadas (implicitas no enunciado):
A lista é duplamente ligada: cada nó tem dois campos/ponteiros chamados tipicamente \text{next} e \text{prev}.
A lista tem \,n\ge 0 elementos (pode ser vazia).
O método deve ser não-recursivo (ou seja, iterativo) e preferencialmente in-place (sem alocar outra lista inteira).
O que deve ser devolvido: o ponteiro para o novo início da lista (novo head).
Casos a tratar explicitamente: lista vazia (n=0) e lista com um elemento (n=1).
Passo 2
Entendendo a estrutura (aula rápida e prática). Um nó de lista duplamente ligada tem, pelo menos, estes campos:
\text{data}: o valor armazenado (não vamos manipular isto para reverter).
\text{next}: ponteiro para o próximo nó (à direita).
\text{prev}: ponteiro para o nó anterior (à esquerda).
Invariante típica antes da inversão (exemplo com três nós):
\text{head} \rightarrow A \xleftrightarrow{\\ \text{next}/\text{prev}\\ } B \xleftrightarrow{\\ \\ } C
ou seja:
A.\text{next}=B, B.\text{prev}=A,
B.\text{next}=C, C.\text{prev}=B,
A.\text{prev}=\mathrm{null} e C.\text{next}=\mathrm{null}.
Objetivo: transformar a lista para que as direções invertam:
\text{new\_head} \rightarrow C \xleftrightarrow{\\ } B \xleftrightarrow{\\ } A
ou seja trocar os papéis de \text{next} e \text{prev} em cada nó e apontar head para o antigo último nó.
Passo 3
Ideia do método (visão intuitiva). Para cada nó da lista trocar os campos \text{next} e \text{prev}. Fazendo isso para todos os nós a orientação da lista inverte. Para percorrer a lista de forma segura durante as trocas, devemos escolher qual ponteiro usar para avançar no loop: após trocar \text{next} e \text{prev} num nó, o ponteiro que antes era \text{next} agora passa a ser \text{prev}. Logo, se antes usávamos \text{next} para avançar nós, após a troca precisamos avançar usando o novo \text{prev} (que contém o antigo \text{next}). Por isso a iteração típica faz:
Para cada nó current:
salvar um auxiliar temp com current.\text{prev} (antes da troca);
trocar current.\text{prev} com current.\text{next};
trocar current.\text{next} com temp (ou atribuir current.\text{next}:=temp);
avançar current para current.\text{prev} (porque depois da troca esse campo contém o próximo nó original).
No final do loop precisamos ajustar head para apontar para o novo início. Há uma pequena subtileza: como usamos temp dentro do loop, o valor final de temp (após o término do loop) nos permite obter o novo head.
Passo 4
Apresentando a rotina em passos detalhados e garantindo que dá para aplicar na prova sem calculadora — aqui é só manipulação de ponteiros. Variáveis usadas:
head: ponteiro para o primeiro nó da lista (entrada).
current: ponteiro usado para percorrer a lista.
temp: ponteiro auxiliar para armazenar temporariamente um campo.
Descrição passo a passo do algoritmo iterativo:
Inicializar current := head e temp := \mathrm{null}.
Enquanto current \neq \mathrm{null} faça:
a. temp := current.\text{prev}. (salva o \text{prev} original)
b. current.\text{prev} := current.\text{next}. (troca \text{prev} pelo \text{next})
c. current.\text{next} := temp. (atribui o \text{next} para o antigo \text{prev})
d. current := current.\text{prev}. (avança: depois da troca, \text{prev} contém o nó que era o \text{next} original)
Ao sair do laço, temp contém o \text{prev} do último nó processado (ou \mathrm{null} se a lista era vazia). Se temp \neq \mathrm{null}, então o novo head é temp.\text{prev}. Caso contrário, a lista era vazia e head continua \mathrm{null}.
Retornar o novo head.
Observação por que fazer head := temp.\text{prev} no final:
Durante a última iteração válida do laço, current aponta para o último nó original (o antigo tail). Depois de processá-lo, fazemos current := current.\text{prev}, que passará a ser \mathrm{null} e o laço termina. Na iteração em que processamos o último nó, temp foi definido como o \text{prev} original daquele último nó; então temp aponta para o nó anterior ao tail original. Após a troca finalizada para o tail original, o campo \text{prev} do tail original passou a apontar para \mathrm{null} ou para o próximo (dependendo do caso), e resulta que o novo head é obtido por temp.\text{prev}. Essa é a forma clássica e compacta usada em muitas implementações. (No passo de pseudocódigo abaixo eu mantenho exatamente essa fórmula.)
Passo 5
Exemplo concreto e passo a passo (muito didático). Comecemos com três nós A,B,C ligados assim (setas \rightarrow mostram \text{next}):
Antes:
A.\text{prev}=\mathrm{null}, A.\text{next}=B
B.\text{prev}=A, B.\text{next}=C
C.\text{prev}=B, C.\text{next}=\mathrm{null}
head=A
Aplicando o algoritmo:
Iteração 1 (current=A):
temp := A.\text{prev} = \mathrm{null}
A.\text{prev} := A.\text{next} = B
A.\text{next} := temp = \mathrm{null}
current := A.\text{prev} = B
Agora A ficou com \text{next}=\mathrm{null} e \text{prev}=B (ou seja, apontando para a direita ao contrário).
Iteração 2 (current=B):
temp := B.\text{prev} = A
B.\text{prev} := B.\text{next} = C
B.\text{next} := temp = A
current := B.\text{prev} = C
Agora B ficou com \text{next}=A e \text{prev}=C.
Iteração 3 (current=C):
temp := C.\text{prev} = B
C.\text{prev} := C.\text{next} = \mathrm{null}
C.\text{next} := temp = B
current := C.\text{prev} = \mathrm{null} — o laço termina.
Ao fim, temp vale B. Então temp.\text{prev} = C (porque em iteração 3 fizemos C.\text{prev} := \mathrm{null} e C.\text{next}:=B, e antes disso B.\text{prev}=C foi ajustado). Assim definimos head := temp.\text{prev} = C. A lista ficou invertida: C \leftrightarrow B \leftrightarrow A.
Passo 6
Complexidade e uso de memória (o que você precisa saber para a prova):
Tempo: cada nó é visitado exatamente uma vez e cada visita faz um número constante de operações (algumas atribuições). Portanto o tempo é O(n).
Espaço: usamos somente um número constante de ponteiros auxiliares (current e temp), logo espaço extra é O(1) (in-place).
Trata corretamente n=0 (lista vazia) e n=1 (lista unitária): o laço é executado zero ou uma vez, e a atribuição final de head preserva comportamento correto.
Passo 7
Prova de corretude (invariante simples):
Invariante do laço: antes de processar um nó current, todos os nós anteriormente processados já tiveram seus \text{next} e \text{prev} trocados, e os nós não processados ainda mantêm a orientação original. Após a troca em current e avançar, a invariante se mantém para o próximo nó. Ao final, todos os nós foram processados e todos os ponteiros invertidos, ou seja, a lista como um todo teve suas direções trocadas. Ajustando head conforme mostrado produz o ponteiro para o antigo tail, que é o novo head. Assim o algoritmo é correto.
Passo 8
Implementação final (pseudocódigo compacto que você pode escrever na prova). Este trecho é o método pedindo no enunciado; ele é não-recursivo, in-place e retorna o novo head.
Resposta
Function ReverseDoublyLinkedList(head):
\begin{array}{l} current := head\\[4pt] temp := \mathrm{null}\\[4pt] \textbf{while } current \neq \mathrm{null} \textbf{ do}\\[4pt] \quad temp := current.\text{prev}\\[4pt] \quad current.\text{prev} := current.\text{next}\\[4pt] \quad current.\text{next} := temp\\[4pt] \quad current := current.\text{prev}\\[4pt] \textbf{end while}\\[4pt] \textbf{if } temp \neq \mathrm{null} \textbf{ then}\\[4pt] \quad head := temp.\text{prev}\\[4pt] \textbf{end if}\\[4pt] \textbf{return } head \end{array}]