0Pricing
Coding Interview Prep · Aula

Revertendo uma Lista Encadeada

Reverta iterativamente uma lista simplesmente encadeada, religando três ponteiros, e faça o mesmo recursivamente, acompanhando cada etapa em um diagrama de quadro branco.

Revertendo uma Lista Encadeada é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.

Por Que a Reversão de Listas é Essencial

Reverter uma lista encadeada está entre as perguntas mais frequentes em entrevistas de programação. Isso testa sua capacidade de manipular ponteiros com precisão sem perder o controle dos nós. Há variações tanto como problemas independentes quanto como etapas de algoritmos maiores, como detecção de palíndromos, reordenação de listas e reversão em grupos de k.

A abordagem iterativa usa três ponteiros: prev, curr e next_node. A abordagem recursiva expressa a mesma lógica como um percurso pela pilha de chamadas. Ambas alcançam tempo O(n) e, na versão iterativa, espaço O(1).

Reversão Iterativa com Três Ponteiros

Em cada etapa da reversão iterativa: salve curr.next para não perder o restante da lista, inverta curr.next para apontar para trás, em direção a prev, avance prev para curr e avance curr para o próximo elemento salvo. Quando curr se torna None, o laço termina e prev é o novo início.

Uma mnemônica útil: Salvar, Inverter, Avançar, Avançar.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node  = curr.next   # Save
        curr.next  = prev        # Flip
        prev       = curr        # Advance prev
        curr       = next_node   # Advance curr
    return prev  # new head

# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
    print(head.val, end=' ')  # 5 4 3 2 1
    head = head.next

Rastreamento Passo a Passo

Vamos rastrear reverse_list em 1 -> 2 -> 3. Inicialmente, prev=None, curr=1. Etapa 1: salve o próximo valor como 2, inverta o ponteiro do nó 1 para nulo; o anterior passa a ser 1 e o atual passa a ser 2. Etapa 2: salve o próximo valor como 3, inverta o ponteiro do nó 2 para 1; o anterior passa a ser 2 e o atual passa a ser 3. Etapa 3: salve o próximo valor como nulo, inverta o ponteiro do nó 3 para 2; o anterior passa a ser 3 e o atual passa a ser nulo. O laço termina; retorne o nó anterior, 3, que é o novo início de 3 -> 2 -> 1.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_traced(head):
    prev, curr = None, head
    step = 0
    while curr:
        step += 1
        next_node = curr.next
        curr.next = prev
        print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
        prev = curr
        curr = next_node
    return prev

nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val)  # 3

Reversão Recursiva

A abordagem recursiva confia que reverse_list(head.next) retorna o novo início do sufixo já revertido. Tudo o que resta é inverter o ponteiro entre head e head.next: defina head.next.next = head (aponte o antigo segundo nó de volta para o antigo primeiro) e head.next = None (rompa o antigo vínculo para a frente). O novo início é propagado a partir do caso-base.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_rec(head):
    # Base case: empty or single node
    if not head or not head.next:
        return head
    new_head = reverse_list_rec(head.next)  # reverse suffix
    head.next.next = head   # former second node points back
    head.next = None        # sever forward link
    return new_head

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
    print(head.val, end=' ')  # 4 3 2 1
    head = head.next

Reversão de uma Sublista (LeetCode 92)

LeetCode 92, «Reverter Lista Encadeada II», solicita que você reverta a sublista da posição esquerda à direita (com indexação a partir de 1) em uma única passagem. O truque consiste em localizar o nó anterior à sublista (use um nó inicial fictício para que isso seja sempre válido), executar a reversão com três ponteiros por exatamente (direita - esquerda) etapas e, por fim, reconectar o segmento revertido à lista ao redor.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head, left, right):
    dummy = ListNode(0, head)
    pre = dummy
    # Advance pre to node just before position 'left'
    for _ in range(left - 1):
        pre = pre.next
    curr = pre.next
    for _ in range(right - left):
        next_node   = curr.next
        curr.next   = next_node.next
        next_node.next = pre.next
        pre.next    = next_node
    return dummy.next

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
    print(head.val, end=' ')  # 1 4 3 2 5
    head = head.next

Reversão de Nós em Grupos de K (LeetCode 25)

LeetCode 25, «Reverter Nós em um Grupo de k», reverte cada grupo consecutivo de k nós. A abordagem é: verifique se ainda restam k nós; caso contrário, deixe-os como estão. Inverta os próximos k nós usando o método iterativo e, em seguida, reverta recursivamente o restante da lista e conecte-o. A complexidade de tempo permanece O(n), com profundidade de chamadas recursivas O(n/k).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    # Check if k nodes are available
    curr, count = head, 0
    while curr and count < k:
        curr = curr.next
        count += 1
    if count < k:
        return head   # fewer than k nodes left, keep as-is
    # Reverse k nodes
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # head is now the tail of the reversed group
    head.next = reverseKGroup(curr, k)
    return prev

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
    print(head.val, end=' ')  # 2 1 4 3 5
    head = head.next

Lista Encadeada Palíndroma

LeetCode 234, «Lista Encadeada Palíndroma»: verifique se uma lista encadeada é um palíndromo em tempo O(n) e espaço O(1). Estratégia: encontre o ponto médio com ponteiros lento e rápido, reverta a segunda metade no próprio local, compare as duas metades nó a nó e, opcionalmente, restaure a lista. Isso combina a localização do ponto médio e a reversão — duas habilidades fundamentais.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Find mid
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Compare
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left  = left.next
        right = right.next
    return True

def build(arr):
    d = ListNode(0)
    c = d
    for v in arr:
        c.next = ListNode(v)
        c = c.next
    return d.next

print(isPalindrome(build([1,2,2,1])))  # True
print(isPalindrome(build([1,2,3])))    # False

Comparação entre Abordagens Iterativa e Recursiva

A reversão iterativa usa espaço O(1) e geralmente é preferível. A reversão recursiva usa espaço de pilha O(n) devido à profundidade das chamadas, o que pode causar um estouro de pilha em listas muito longas (o limite padrão do Python é de aproximadamente 1000 níveis de recursão).

Em uma entrevista, implemente primeiro a versão iterativa para demonstrar que você entende as restrições de espaço; em seguida, mencione a versão recursiva como uma alternativa mais limpa caso o comprimento da lista seja limitado.

import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint

# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)

Erros Comuns na Reversão

Três erros são responsáveis por quase todos os problemas de reversão. Primeiro, não salvar o próximo antes de sobrescrevê-lo: curr.next = prev destrói a referência para a frente se o nó seguinte não tiver sido salvo. Segundo, não retornar o nó anterior: no fim do laço, o nó atual é nulo, mas o nó anterior é o novo início. Terceiro, caso-base recursivo incorreto: esquecer not head.next significa que uma lista de um único nó não é tratada e causa um AttributeError.

# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next   # BUG if omitted: lose rest of list
        curr.next = prev
        prev      = curr
        curr      = next_node
    return prev               # BUG if you return curr: it is None

nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
    print(h.val, end=' ')  # 3 2 1
    h = h.next

Reordenar a Lista (LeetCode 143)

LeetCode 143, «Reordenar a Lista», reorganiza L0 → L1 → L2 → ... → Ln em L0 → Ln → L1 → Ln-1 → L2 → Ln-2 em tempo O(n) e espaço O(1). A solução combina três etapas: encontrar o ponto médio, reverter a segunda metade e intercalar as duas metades. Dominar a reversão transforma esse problema aparentemente complexo em uma combinação direta de ferramentas conhecidas.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    # Find mid
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Interleave
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
    print(h.val, end=' ')  # 1 4 2 3
    h = h.next

Resumo: a Reversão é um Componente Fundamental

A reversão de listas encadeadas raramente é o objetivo final — ela é um componente fundamental. A detecção de palíndromos, a reversão em grupos de k, a reordenação de listas e a reversão entre posições dependem do mesmo padrão iterativo de três ponteiros. Quando o padrão se torna automático, você pode concentrar sua capacidade mental na estrutura do problema em um nível mais alto.

Pratique sempre a reversão até conseguir escrevê-la de memória em menos de dois minutos; ela aparecerá de alguma forma em praticamente toda rodada de entrevistas sobre listas encadeadas.

Verificação Rápida

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.

Recapitulação da Lição

Nesta lição, você aprendeu: o padrão iterativo Salvar-Inverter-Avançar-Avançar reverte uma lista em tempo O(n) e espaço O(1), a abordagem recursiva confia que o sufixo já está invertido e corrige apenas o último vínculo e a reversão é uma subetapa fundamental na detecção de palíndromos, na reordenação de listas e na reversão em grupos de k. A seguir, exploraremos a detecção de ciclos com o algoritmo de Floyd.

Perguntas Frequentes

A aula “Revertendo uma Lista Encadeada” é grátis?

Sim — o texto completo de “Revertendo uma Lista Encadeada” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.

O que vou aprender em “Revertendo uma Lista Encadeada”?

Reverta iterativamente uma lista simplesmente encadeada, religando três ponteiros, e faça o mesmo recursivamente, acompanhando cada etapa em um diagrama de quadro branco. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Coding Interview Prep?

Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.

Quanto tempo leva a aula “Revertendo uma Lista Encadeada”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Coding Interview Prep?

Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Classe Node e Construção de Listas
  2. Revertendo uma Lista Encadeada
  3. Detecção de Ciclos com o Algoritmo de Floyd
  4. Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim
← Voltar para Coding Interview Prep