0x70Lição 8 de 13

Religue listas ligadas

Inverta, mescle e detecte ciclos movendo os ponteiros dos nós com cuidado.

20 min Questionário com 5 perguntas 1 exercício de código

Ao final desta lição, você saberá

Inverter uma lista ligada de forma iterativa.
Usar ponteiros rápido e lento para encontrar o meio ou detectar um ciclo.
Simplificar casos extremos com um nó cabeça fictício (dummy head).

Uma lista ligada é uma cadeia de nós, e cada um guarda um valor e uma referência para o próximo nó. Inserir ou remover um nó que você já tem em mãos é O(1), mas chegar ao k-ésimo nó leva O(k). As perguntas de lista ligada testam se você consegue manipular referências sem perder parte da lista - então desenhe as caixas e as setas enquanto avança.

Técnicas principais

Inversão iterativa: percorra a lista com prev, current e um next guardado, apontando cada nó de volta para prev.
Ponteiros rápido e lento: mova um ponteiro dois passos e o outro um passo. Quando o rápido chega ao fim, o lento está no meio. Se o rápido encontrar o lento em algum momento, a lista tem um ciclo (algoritmo de Floyd).
Dummy head: comece a lista de resultado com um nó marcador, para que inserir no começo não precise de caso especial; devolva dummy.next.

solution.py

1class Node:
2    def __init__(self, value, next=None):
3        self.value = value
4        self.next = next
5
6def reverse(head):
7    prev = None
8    current = head
9    while current:
10        next_node = current.next  # save before rewiring
11        current.next = prev
12        prev = current
13        current = next_node
14    return prev
15
16head = Node(1, Node(2, Node(3)))
17node = reverse(head)
18while node:
19    print(node.value, end=" ")
20    node = node.next
21print()

Saída

3 2 1

A ordem das quatro atribuições dentro do laço importa: guarde current.next primeiro, ou o resto da lista se perde no instante em que você religa current. A inversão é O(n) de tempo e O(1) de espaço extra. Uma versão recursiva é mais curta, mas usa O(n) de espaço na pilha.

Principais conclusões

Guarde o next antes de religar um nó.
Ponteiros rápido/lento encontram o meio e detectam ciclos com espaço O(1).
Um dummy head remove casos especiais ao construir listas.

Quiz da aula

5 perguntas · aprovação com 4 acertos · até 50 XP

Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.

Pratique: resolva problemas de entrevistas técnicas

Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.

Exercício 1

Inverta uma lista ligada

+25 XP

O código inicial monta uma lista ligada a partir de uma linha de valores. Inverta-a religando os nós (não invertendo a lista do Python) e depois imprima os valores a partir da nova cabeça, separados por espaços.

Cinco nós
Um nó só

main.py

Carregando editor…

O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.

Dúvidas sobre esta lição

Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.

Carregando publicações…