0Pricing
DSA Interview Prep · Aula

Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim

Intercale duas listas encadeadas ordenadas em O(n), divida uma lista no ponto médio usando ponteiros lento e rápido e encontre o n-ésimo nó a partir do final.

Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 4 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.

Três Padrões Essenciais de Listas Encadeadas

Esta lição aborda três operações fundamentais de listas encadeadas que aparecem constantemente como componentes de problemas mais difíceis: mesclar duas listas ordenadas (usado na ordenação por mesclagem e na mesclagem em k vias), dividir uma lista em seu ponto médio (usado na ordenação por mesclagem e na detecção de palíndromos) e encontrar o n-ésimo nó a partir do fim (usado na remoção do n-ésimo nó a partir do fim).

As três operações dependem de técnicas que você já viu: o nó inicial fictício, os ponteiros lento e rápido e o controle cuidadoso dos limites.

Mesclando Duas Listas Ordenadas

LeetCode 21, «Mesclar Duas Listas Ordenadas»: dadas duas listas encadeadas ordenadas, retorne uma única lista encadeada ordenada mesclada. Use um nó inicial fictício e um ponteiro de cauda curr. A cada etapa, compare os nós iniciais das duas listas e anexe o menor nó a curr. Quando uma lista se esgotar, anexe o restante da outra. Tempo: O(n+m), Espaço: O(1) (reconfiguração no próprio local).

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

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2  # attach remaining nodes
    return dummy.next

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

def to_list(h):
    r=[]
    while h: r.append(h.val); h=h.next
    return r

print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))

Rastreando a Mesclagem Passo a Passo

Rastreie mergeTwoLists([1,2,4], [1,3,4]): compare 1 e 1 — escolha 1 da primeira lista e avance a primeira lista para 2. Compare 2 e 1 — escolha 1 da segunda lista e avance a segunda lista para 3. Compare 2 e 3 — escolha 2 da primeira lista e avance a primeira lista para 4. Compare 4 e 3 — escolha 3 da segunda lista e avance a segunda lista para 4. Compare 4 e 4 — escolha 4 da primeira lista e avance a primeira lista para nulo. Anexe o 4 restante da segunda lista. Resultado: [1,1,2,3,4,4].

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

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    step  = 0
    while l1 and l2:
        step += 1
        if l1.val <= l2.val:
            print(f'Step {step}: pick l1({l1.val})')
            curr.next = l1; l1 = l1.next
        else:
            print(f'Step {step}: pick l2({l2.val})')
            curr.next = l2; l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

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

mergeTwoLists(build([1,2,4]),build([1,3,4]))

Encontrando o Ponto Médio com Ponteiros Lento e Rápido

Para dividir uma lista em seu ponto médio, use o padrão de ponteiros lento e rápido. slow avança 1 etapa; fast avança 2 etapas. Quando o ponteiro rápido alcança o valor nulo (ou o último nó), o ponteiro lento está no ponto médio. Para uma lista de comprimento par, isso fornece o primeiro dos dois nós centrais, o que é convencional na divisão para a ordenação por mesclagem.

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

def split_at_mid(head):
    '''Returns (first_half_head, second_half_head).'''
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next   # second half starts here
    slow.next = None  # sever the list
    return head, mid

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

def to_list(h):
    r=[]
    while h: r.append(h.val); h=h.next
    return r

head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second))  # [1,2,3] [4,5]

Ordenação por mesclagem em uma lista encadeada

LeetCode 148 'Ordenar lista': ordene uma lista encadeada em tempo O(n log n) e espaço O(log n). A abordagem consiste em dividir a lista no ponto médio, ordenar recursivamente cada metade e mesclá-las. A ordenação por mesclagem de listas encadeadas é natural porque dividir no ponto médio custa O(n) (e não O(1), como em vetores), mas a complexidade geral continua sendo O(n log n), usando apenas O(log n) de espaço na pilha.

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

def sortList(head):
    if not head or not head.next:
        return head
    # Split
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    # Recurse
    left  = sortList(head)
    right = sortList(mid)
    # Merge
    dummy = ListNode(0)
    curr  = dummy
    while left and right:
        if left.val <= right.val:
            curr.next = left;  left  = left.next
        else:
            curr.next = right; right = right.next
        curr = curr.next
    curr.next = left or right
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(sortList(build([4,2,1,3]))))  # [1,2,3,4]

Encontrando o n-ésimo nó a partir do fim

LeetCode 19 'Remover o n-ésimo nó do fim da lista': encontre o n-ésimo nó a partir da cauda em uma única passagem. Use dois ponteiros separados por exatamente n nós. Avance fast n passos à frente de slow. Em seguida, avance ambos juntos até que fast alcance o último nó. Nesse ponto, slow está no (n+1)º nó a partir do fim — o predecessor do nó a ser removido.

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

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    for _ in range(n + 1):  # advance fast n+1 steps
        fast = fast.next
    slow = dummy
    while fast:             # advance both until fast is None
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next  # remove nth node
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2)))  # [1,2,3,5]

Por que são necessários n+1 passos ao remover o n-ésimo nó

A sutileza principal é avançar fast em n+1 passos (e não n) a partir da cabeça fictícia. Após n+1 passos, fast está n+1 posições à frente de slow (ambos começam na cabeça fictícia). Quando fast chega a nulo (uma posição depois da cauda), slow está n+1 posições antes de nulo — o que significa que slow está na posição (comprimento - n - 1), contando a partir de zero, ou seja, no predecessor do alvo. Isso permite que slow.next = slow.next.next exclua o n-ésimo nó a partir do fim de forma simples.

# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow)  1  2  3(fast)  4  5  None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')

Interseção de duas listas encadeadas

LeetCode 160 'Interseção de duas listas encadeadas': encontre o nó em que duas listas se intersectam pela primeira vez. O truque de espaço O(1): avance dois ponteiros, um por lista. Quando um ponteiro chega a nulo, redirecione-o para a cabeça da outra lista. Após, no máximo, len(A) + len(B) passos, ambos os ponteiros terão percorrido a mesma distância total e deverão estar no nó de interseção (ou ambos em nulo, se não houver interseção).

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

def getIntersectionNode(headA, headB):
    a, b = headA, headB
    while a is not b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # None if no intersection

# Build: A: 4->1->\  B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val)  # 8

Mesclando K listas ordenadas (divisão e conquista)

LeetCode 23 'Mesclar K listas ordenadas': dadas k listas ordenadas, mescle-as em uma só. A abordagem ideal é mesclar repetidamente pares de listas usando divisão e conquista, reduzindo pela metade o número de listas a cada rodada. Com k listas de comprimento médio n, isso leva tempo O(n k log k), em comparação com O(n k²) da mesclagem sequencial. Uma abordagem com heap mínimo também custa O(n k log k).

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

def mergeKLists(lists):
    def merge_two(l1, l2):
        dummy = ListNode(0); curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1; l1 = l1.next
            else:
                curr.next = l2; l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

    if not lists: return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i+1] if i+1 < len(lists) else None
            merged.append(merge_two(l1, l2))
        lists = merged
    return lists[0]

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists)))  # [1,1,2,3,4,4,5,6]

Lista encadeada de índices ímpares e pares

LeetCode 328 'Lista encadeada de índices ímpares e pares': agrupe primeiro todos os nós cujos índices são ímpares e depois os de índices pares (começando a contagem em 1). A abordagem consiste em manter duas cadeias separadas (ímpar e par) e conectá-las ao final. Uma única passagem pela lista é suficiente, resultando em tempo O(n) e espaço O(1). Este é um exemplo claro de como avançar simultaneamente dois ponteiros com passos diferentes.

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

def oddEvenList(head):
    if not head:
        return head
    odd  = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next  = even.next
        odd       = odd.next
        even.next = odd.next
        even      = even.next
    odd.next = even_head
    return head

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(oddEvenList(build([1,2,3,4,5]))))  # [1,3,5,2,4]

Juntando tudo

Os três padrões desta lição — mesclar listas ordenadas, dividir no ponto médio e encontrar o n-ésimo nó a partir do fim — compartilham um tema comum: use variáveis de ponteiro adicionais para acompanhar posições sem memória extra. A cabeça fictícia simplifica a mesclagem e a exclusão; a distância entre os ponteiros lento e rápido fixa uma posição relativa específica; avançar primeiro um ponteiro cria a separação desejada.

Em uma entrevista, nomeie o padrão que está usando antes de programar: "Usarei a técnica da distância entre dois ponteiros para encontrar o n-ésimo nó a partir do fim em uma única passagem." Isso demonstra raciocínio estruturado.

Verificação rápida

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

Resumo da lição

Nesta lição, você aprendeu que: mesclar duas listas ordenadas usa uma cabeça fictícia e comparação a cada etapa, com O(n+m) de tempo e O(1) de espaço, dividir no ponto médio usa ponteiros lento e rápido, com fast parando no último par válido e encontrar o n-ésimo nó a partir do fim requer avançar fast n+1 passos à frente para que slow pare no predecessor. A seguir, construiremos pilhas e filas e as aplicaremos a problemas clássicos de entrevistas.

Perguntas Frequentes

A aula “Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim” é grátis?

Sim — o texto completo de “Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.

O que vou aprender em “Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim”?

Intercale duas listas encadeadas ordenadas em O(n), divida uma lista no ponto médio usando ponteiros lento e rápido e encontre o n-ésimo nó a partir do final. Você pratica DSA 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 DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA 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 4 de 4.

Quanto tempo leva a aula “Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim”?

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 DSA Interview Prep?

Sim. Cada aula de DSA 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 DSA Interview Prep