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:
  1. Inicializar current := head e temp := \mathrm{null}.
  2. 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)
  3. 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}.
  4. 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}]

Exercícios relacionados