OCS Forum

← Back to home

Linked List

By Pscodium · 8/4/2026 · 6 views

LeetCodeLinked List

Linked List — Entendendo Listas Encadeadas

Linked List (lista encadeada) é uma estrutura de dados formada por uma sequência de elementos chamados nós (Nodes).

Diferente de um array, em que os elementos ficam armazenados em posições consecutivas de memória, cada elemento de uma Linked List possui uma referência para o próximo elemento.

A estrutura pode ser visualizada assim:

[10] → [20] → [30] → [40] → null

Cada bloco é um Node.

O último nó aponta para:

null

indicando que chegamos ao final da lista.

Linked Lists aparecem frequentemente em problemas do LeetCode e são importantes para entender conceitos como:

  • Ponteiros e referências
  • Estruturas dinâmicas
  • Recursão
  • Two Pointers
  • Fast & Slow Pointers
  • Manipulação de nós
  • Estruturas de dados

1. O que é um Node?

Um Node representa um elemento da lista.

Em uma Linked List simples, cada Node possui:

value
next

Por exemplo:

[10 | next] → [20 | next] → [30 | null]

O value guarda o valor:

10

E o next guarda uma referência para o próximo Node.

Em TypeScript:

class ListNode {
  value: number;
  next: ListNode | null;

  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

Podemos criar uma lista:

const first = new ListNode(10);
const second = new ListNode(20);
const third = new ListNode(30);

first.next = second;
second.next = third;

Agora temos:

first
  ↓
[10] → [20] → [30] → null

O first representa o início da lista.

Normalmente chamamos esse primeiro nó de:

head

2. O que é o Head?

O Head é o primeiro nó de uma Linked List.

Por exemplo:

head
 ↓
[10] → [20] → [30] → null

Se quisermos acessar o primeiro elemento:

head.value

Resultado:

10

Para acessar o próximo:

head.next

Temos:

[20]

E:

head.next.next

resulta em:

[30]

Podemos continuar percorrendo a lista seguindo o next.

3. Percorrendo uma Linked List

Para percorrer uma lista, normalmente criamos uma variável que começa no head.

let current = head;

while (current !== null) {
  console.log(current.value);

  current = current.next;
}

Para:

[10] → [20] → [30] → null

Teremos:

10
20
30

O funcionamento é:

current
   ↓
[10] → [20] → [30]

Depois:

         current
            ↓
[10] → [20] → [30]

Depois:

                 current
                    ↓
[10] → [20] → [30]

Depois:

current = null

E o loop termina.

Esse padrão é extremamente importante para resolver problemas de Linked List.

4. Linked List vs Array

Considere um array:

const numbers = [10, 20, 30, 40];

Podemos acessar diretamente:

numbers[2];

Resultado:

30

Isso é possível porque o array possui acesso por índice.

Em uma Linked List:

[10] → [20] → [30] → [40]

Para chegar ao 30, precisamos percorrer:

10
 ↓
20
 ↓
30

Não podemos simplesmente fazer:

list[2];

5. Complexidade

A diferença pode ser resumida assim:

OperaçãoArrayLinked ListAcesso por índiceO(1)O(n)BuscaO(n)O(n)Inserção no inícioO(n)O(1)Remoção no inícioO(n)O(1)Inserção após um nó conhecidoO(n)O(1)Memória extra por elementoBaixaMaior

A Linked List possui uma vantagem importante:

Inserir ou remover nós pode ser muito eficiente quando já temos uma referência para a posição correta.

Por exemplo:

[10] → [20] → [30]

Queremos inserir 25 entre 20 e 30.

Antes:

[10] → [20] → [30]

Criamos:

[25]

Alteramos as referências:

[10] → [20] → [25] → [30]

Não precisamos mover os outros elementos.

6. Inserindo um Node

Imagine:

current
   ↓
[20] → [30]

Criamos:

newNode = [25]

Primeiro:

newNode.next = current.next;

Temos:

[20] → [30]

[25] → [30]

Depois:

current.next = newNode;

Resultado:

[20] → [25] → [30]

Código completo:

const newNode = new ListNode(25);

newNode.next = current.next;
current.next = newNode;

A operação é:

O(1)

desde que já tenhamos acesso ao nó current.

7. O problema clássico do LeetCode: Reverse Linked List

Um dos problemas mais conhecidos do LeetCode é:

Reverse Linked List

Temos:

[1] → [2] → [3] → [4] → null

Precisamos transformar em:

[4] → [3] → [2] → [1] → null

A ideia é inverter as referências.

Inicialmente:

null ← [1] → [2] → [3] → [4] → null
       ↑
     current

Precisamos fazer:

[1] → null

Depois:

[2] → [1] → null

Depois:

[3] → [2] → [1] → null

E assim por diante.

8. Reverse Linked List com dois ponteiros

Precisamos de duas variáveis:

previous
current

Começamos:

previous = null

current = [1]

Visualmente:

previous
   ↓
 null

current
   ↓
[1] → [2] → [3] → [4]

Precisamos guardar o próximo nó antes de alterar a referência.

const next = current.next;

Agora:

next
 ↓
[2] → [3] → [4]

Podemos inverter:

current.next = previous;

Agora:

[1] → null

Movemos os ponteiros:

previous = current;
current = next;

Agora:

previous
   ↓
[1] → null

current
   ↓
[2] → [3] → [4]

Repetimos o processo.

9. Implementação do Reverse Linked List

function reverseList(
  head: ListNode | null
): ListNode | null {
  let previous: ListNode | null = null;
  let current = head;

  while (current !== null) {
    const next = current.next;

    current.next = previous;

    previous = current;
    current = next;
  }

  return previous;
}

Se tivermos:

[1] → [2] → [3] → [4] → null

O resultado será:

[4] → [3] → [2] → [1] → null

Complexidade:

Time: O(n)

Space: O(1)

Esse é um excelente exemplo de como uma Linked List exige que pensemos em referências, e não apenas em valores.

10. O problema de perder o próximo Node

Existe um detalhe muito importante.

Imagine:

[1] → [2] → [3]

Se fizermos:

current.next = previous;

antes de guardar o próximo nó, perdemos a referência para:

[2]

Por isso fazemos:

const next = current.next;

Antes de alterar:

current.next = previous;

A ordem é:

1. Guardar o próximo
2. Inverter a referência
3. Avançar previous
4. Avançar current

O padrão é:

next = current.next

current.next = previous

previous = current

current = next

Essa sequência é extremamente importante em problemas de Linked List.

11. Fast & Slow Pointers

Outro padrão muito comum é utilizar dois ponteiros:

slow
fast

O slow anda um passo por vez.

O fast anda dois passos.

Imagine:

[1] → [2] → [3] → [4] → [5]
 ↑
slow
 ↑
fast

Depois de uma iteração:

[1] → [2] → [3] → [4] → [5]
       ↑         ↑
      slow      fast

Depois:

[1] → [2] → [3] → [4] → [5]
              ↑
             slow

                        ↑
                       fast

Quando fast chega ao final, slow estará aproximadamente no meio.

12. Encontrando o meio da Linked List

Esse é outro problema clássico:

Middle of the Linked List

Dada:

[1] → [2] → [3] → [4] → [5]

Queremos:

3

Podemos fazer:

function middleNode(
  head: ListNode | null
): ListNode | null {
  let slow = head;
  let fast = head;

  while (
    fast !== null &&
    fast.next !== null
  ) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  return slow;
}

O resultado será:

[3] → [4] → [5]
 ↑
slow

A ideia é:

slow → 1 passo

fast → 2 passos

Quando fast percorreu toda a lista:

slow
 ↓
meio da lista

Complexidade:

Time: O(n)

Space: O(1)

13. Detectando ciclos

Imagine que temos:

[1] → [2] → [3] → [4]
             ↑       ↓
             └───────┘

O nó 4 aponta novamente para 3.

Temos um ciclo.

Se simplesmente fizermos:

while (current !== null) {
  current = current.next;
}

nunca chegaremos a null.

O algoritmo ficará executando infinitamente.

Podemos detectar o ciclo usando Fast & Slow Pointers.

14. Floyd's Cycle Detection

A técnica é conhecida como:

Floyd's Tortoise and Hare Algorithm

Temos:

slow

que anda um passo.

E:

fast

que anda dois passos.

Se existir um ciclo, eventualmente eles irão se encontrar.

slow → 1 passo

fast → 2 passos

Em uma lista sem ciclo:

fast → null

Em uma lista com ciclo:

slow
  ↓
[1] → [2] → [3] → [4]
             ↑       ↓
             └───────┘
                  ↑
                 fast

Depois de algum tempo:

slow === fast

15. Implementação

function hasCycle(
  head: ListNode | null
): boolean {
  let slow = head;
  let fast = head;

  while (
    fast !== null &&
    fast.next !== null
  ) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

Se:

slow === fast

temos um ciclo.

Se:

fast === null

ou:

fast.next === null

não existe ciclo.

Complexidade:

Time: O(n)

Space: O(1)

16. Por que eles eventualmente se encontram?

Imagine uma pista circular.

O slow está andando:

1 passo

O fast está andando:

2 passos

Como os dois estão presos no mesmo ciclo, o fast eventualmente alcançará o slow.

É semelhante a duas pessoas correndo em uma pista circular:

slow → 🐢

fast → 🐇

Mesmo que comecem em posições diferentes, quem corre mais rápido eventualmente alcança quem está mais devagar.

17. Linked List como uma cadeia de referências

Uma maneira importante de entender Linked Lists é parar de pensar nelas como um array.

Array:

[10, 20, 30, 40]

Linked List:

[10]
  ↓
[20]
  ↓
[30]
  ↓
[40]
  ↓
null

Cada Node possui uma referência:

value
  +
next

Então:

Node 1
   │
   ├── value = 10
   │
   └── next ──────┐
                  ↓
               Node 2

Essa forma de pensar é essencial para resolver problemas de Linked List.

18. Uma aplicação prática: fila

Uma Linked List pode ser utilizada para implementar estruturas como uma Queue.

Imagine uma fila:

Pessoa A
   ↓
Pessoa B
   ↓
Pessoa C

A primeira pessoa que entrou é a primeira a sair.

Isso é:

FIFO

First In
First Out

Podemos representar:

head
 ↓
[A] → [B] → [C] → null

Remover o primeiro elemento é simplesmente mover o head:

head
 ↓
[B] → [C] → null

A operação pode ser:

O(1)

Com uma referência para o final da lista, também podemos inserir no final de maneira eficiente.

19. Singly Linked List

O exemplo que vimos até agora é uma:

Singly Linked List

Cada nó aponta apenas para o próximo:

[10] → [20] → [30] → null

A estrutura do Node é:

class ListNode {
  value: number;
  next: ListNode | null;
}

Só conseguimos navegar:

10 → 20 → 30

Não conseguimos voltar diretamente:

30 → 20

porque 30 não possui uma referência para 20.

20. Doubly Linked List

Uma Doubly Linked List possui duas referências:

previous
next

Podemos visualizar:

null ← [10] ⇄ [20] ⇄ [30] → null

Cada nó conhece:

anterior
+
próximo

Uma implementação:

class DoublyNode {
  value: number;

  previous: DoublyNode | null;

  next: DoublyNode | null;

  constructor(value: number) {
    this.value = value;
    this.previous = null;
    this.next = null;
  }
}

Agora podemos navegar:

10 → 20 → 30

e também:

30 → 20 → 10

Isso facilita algumas operações, mas exige mais memória.

21. Linked List Circular

Também existe a:

Circular Linked List

Nesse caso, o último elemento aponta novamente para o primeiro.

      ┌─────────────────┐
      ↓                 │
[10] → [20] → [30] → [40]

Em vez de:

[40] → null

temos:

[40] → [10]

Esse conceito pode ser utilizado em:

  • Sistemas de turnos
  • Round Robin
  • Filas circulares
  • Sistemas de agendamento

22. Linked List e o LeetCode

Linked Lists aparecem frequentemente em entrevistas técnicas.

Alguns problemas clássicos são:

Reverse Linked List

[1] → [2] → [3]

↓

[3] → [2] → [1]

Middle of the Linked List

Encontrar o nó central:

[1] → [2] → [3] → [4] → [5]

↓

[3]

Linked List Cycle

Verificar se existe um ciclo:

[1] → [2] → [3]
          ↑     ↓
          └─────┘

Merge Two Sorted Lists

Combinar:

[1] → [3] → [5]

[2] → [4] → [6]

Resultando em:

[1] → [2] → [3] → [4] → [5] → [6]

Remove Nth Node From End

Dada:

[1] → [2] → [3] → [4] → [5]

Remover o segundo nó a partir do final:

[1] → [2] → [3] → [5]

Esse problema também pode ser resolvido utilizando dois ponteiros.

23. O padrão Dummy Node

Um truque muito útil em problemas de Linked List é criar um nó fictício:

dummy
  ↓
[0] → [1] → [2] → [3]

O dummy não faz parte dos dados reais.

Ele serve para simplificar operações que envolvem o head.

Por exemplo, remover o primeiro elemento normalmente exige um tratamento especial:

if (head === target) {
  head = head.next;
}

Com um dummy, podemos tratar todos os elementos de maneira semelhante.

const dummy = new ListNode(0);

dummy.next = head;

Agora temos:

dummy → head → ...

No final:

return dummy.next;

Esse padrão aparece frequentemente em problemas de:

  • Remoção de nós
  • Merge de listas
  • Inserção
  • Manipulação de listas

24. Exemplo: Merge Two Sorted Lists

Temos:

list1:

[1] → [3] → [5]


list2:

[2] → [4] → [6]

Queremos:

[1] → [2] → [3] → [4] → [5] → [6]

Podemos utilizar um dummy.

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);

  let current = dummy;

  while (
    list1 !== null &&
    list2 !== null
  ) {
    if (list1.value <= list2.value) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }

    current = current.next;
  }

  current.next = list1 ?? list2;

  return dummy.next;
}

Resultado:

[1] → [2] → [3] → [4] → [5] → [6]

Complexidade:

Time: O(n + m)

Space: O(1)

25. Os principais padrões para memorizar

Quando encontrar um problema de Linked List, alguns padrões aparecem com frequência.

Percorrer a lista

let current = head;

while (current !== null) {
  current = current.next;
}

Inverter a lista

let previous = null;
let current = head;

Usar:

previous
current
next

Encontrar o meio

Usar:

slow
fast

Onde:

slow → 1 passo

fast → 2 passos

Detectar ciclo

Usar:

slow
fast

Se:

slow === fast

existe um ciclo.

Simplificar operações

Usar:

dummy node

26. Como pensar em problemas de Linked List

Quando encontrar um problema, tente fazer as seguintes perguntas:

1. Preciso percorrer a lista?

Use:

current

2. Preciso inverter a lista?

Pense em:

previous
current
next

3. Preciso encontrar o meio?

Pense em:

slow
fast

4. Preciso detectar um ciclo?

Pense em:

Fast & Slow Pointers

5. Preciso inserir/remover elementos?

Pense em:

next
previous
dummy node

6. Preciso comparar duas listas?

Pense em:

pointer1
pointer2

Conclusão

Uma Linked List é uma estrutura de dados composta por nós conectados por referências.

A estrutura mais simples é:

[Node] → [Node] → [Node] → null

Cada Node possui:

value
next

As principais operações e técnicas que você deve conhecer são:

Percorrer
    ↓
current

Inverter
    ↓
previous + current + next

Encontrar o meio
    ↓
slow + fast

Detectar ciclo
    ↓
Floyd's Algorithm

Manipular início da lista
    ↓
dummy node

Os conceitos mais importantes para problemas de Linked List são:

  • Entender referências entre nós
  • Saber manipular next
  • Não perder referências ao alterar ponteiros
  • Utilizar Fast & Slow Pointers
  • Saber inverter uma lista
  • Entender como detectar ciclos
  • Utilizar Dummy Nodes para simplificar operações

A principal diferença para um array é que uma Linked List não foi projetada para acesso rápido por índice. Em compensação, quando temos a referência correta para um nó, podemos modificar as conexões entre os elementos de maneira muito eficiente.

Em problemas de Linked List, o valor dos nós é apenas parte do problema. Na maioria das vezes, o verdadeiro desafio é manipular corretamente as referências que conectam um nó ao outro.


Comments

No comments yet.