Intersection of Two Linked Lists

+10

Duas listas simplesmente encadeadas estão armazenadas em um único conjunto de nós. O nó i aponta para o nó next[i], e -1 encerra uma lista. A lista A começa no nó headA e a lista B, no nó headB. Os nós não estão armazenados em uma ordem específica, então siga os apontadores.

As duas listas podem se encontrar: a partir de algum nó, elas continuam pelos mesmos nós até o fim. Retorne o índice do primeiro nó que está nas duas listas, ou -1 se elas não compartilharem nenhum nó.

Função

getIntersectionNode(next: integer-array, headA: integer, headB: integer) → integer

nextinteger-array: o índice do nó ao qual cada nó está ligado, ou -1 para o último nó de uma lista
headAinteger: o primeiro nó da lista A
headBinteger: o primeiro nó da lista B
Retornainteger: o primeiro nó compartilhado pelas duas listas, ou -1

Restrições

2 ≤ n ≤ 10⁴, em que n é o comprimento de next.
Cada next[i] é -1 ou um índice de nó de 0 a n-1.
0 ≤ headA, headB ≤ n-1 e headA ≠ headB.
Ambas as listas terminam em -1 sem visitar um nó duas vezes. Não há ciclo.
Cada nó está na lista A, na lista B ou em ambas.

Exemplos

Entrada: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Saída: 1
Explicação: A visita 3, 5, 1, 4, 0 e B visita 2, 1, 4, 0. A partir do nó 1, eles compartilham todos os nós, e nenhum nó anterior de A está em B, então a resposta é 1.

Entrada: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Saída: -1
Explicação: A lista A é 0, 2, 4 e a lista B é 1, 3. Ambas terminam em -1 sem tocar em um nó comum, então a resposta é -1.

Entrada: next = [3, 2, 0, -1]headA = 1headB = 0
Saída: 0
Explicação: A lista A é 1, 2, 0, 3 e a lista B é 0, 3. A lista B é a cauda da lista A, então o primeiro nó compartilhado é o próprio headB, nó 0.

Para ir além

Você consegue encontrar o nó em tempo O(m + k) com memória extra O(1)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um nó tem um next, então duas listas que se encontram nunca mais se separam. Elas formam um Y: dois inícios privados unidos a uma cauda compartilhada, e a resposta é a junção. Os inícios podem ter comprimentos diferentes, então avançar pelas duas listas juntas faz com que a junção não seja encontrada. Abaixo, m e k são os comprimentos de A e B.

Verifique cada nó de A em relação a todos os nós de B

Correta, mas não termina nos maiores testes

Intuição

Um ponteiro é um índice de nó, e avançar é node = next[node]. Para cada nó a de A, em ordem, percorra todo B e compare cada nó com a. O primeiro a que corresponder é a resposta, porque todos os nós anteriores de A já falharam. Isso percorre B novamente para cada nó de A: com 5000 nós em cada lista e nenhum nó compartilhado, são 2.5 × 10^7 comparações.

Algoritmo

Defina a = headA.
Enquanto a não for -1, percorra b de headB até -1.
Se b == a em algum momento, retorne a.
Caso contrário, avance a = next[a] e repita.
Se a lista A acabar, retorne -1.

def getIntersectionNode(next, headA, headB):
    a = headA
    while a != -1:
        # Is node a also on list B? Walk all of B to find out.
        b = headB
        while b != -1:
            if a == b:
                return a
            b = next[b]
        a = next[a]
    return -1

Marque os nós da lista B

Intuição

Responda “este nó está em B?” uma vez para cada nó: percorra B e marque cada nó em um array booleano de tamanho n. Os índices dos nós são números inteiros pequenos, então um array dá conta do recado como um conjunto hash. Em seguida, percorra A a partir de sua cabeça. O primeiro nó marcado está nas duas listas, e é o primeiro nó assim encontrado porque você percorre A em ordem. No primeiro exemplo, B marca 2, 1, 4, 0, e o percurso em A passa por 3 e 5 antes de parar em 1. Cada lista é percorrida uma vez, então o tempo é O(m + k), ao custo de n marcações.

Algoritmo

Crie onB, um array de n booleanos definidos como false.
Percorra a lista B a partir de headB e defina onB[node] = true para cada nó.
Percorra a lista A a partir de headA. Retorne o primeiro nó com onB[node] true.
Se a lista A terminar, retorne -1.

def getIntersectionNode(next, headA, headB):
    # Mark every node of list B.
    on_b = [False] * len(next)
    node = headB
    while node != -1:
        on_b[node] = True
        node = next[node]
    # The first marked node on list A is the meeting point.
    node = headA
    while node != -1:
        if on_b[node]:
            return node
        node = next[node]
    return -1

Dois ponteiros que alternam entre listas

Intuição

Divida cada lista no ponto de junção: A tem x nós privados e depois os c nós compartilhados, e B tem y nós privados e depois os mesmos c. O ponteiro a percorre A, passa por -1, depois recomeça em headB e alcança o ponto de junção pela segunda vez após x + c + 1 + y movimentos. O ponteiro b percorre B e depois A, chegando após y + c + 1 + x movimentos. Os totais são iguais. No primeiro exemplo, x = 2, y = 1 e c = 3, e ambos ficam no nó 1 após sete movimentos.

Sem uma cauda compartilhada, ambos os ponteiros ficam em -1 após m + 1 + k movimentos (após m quando m = k), e o loop retorna -1. Essa parada comum é o motivo pelo qual cada ponteiro passa por -1 antes de trocar. Cada ponteiro se move no máximo m + k + 1 vezes, com dois índices de memória.

Algoritmo

Defina a = headA e b = headB.
Enquanto a != b: mova a para headB se ele for -1; caso contrário, para next[a].
Na mesma rodada, mova b para headA se ele for -1; caso contrário, para next[b].
Quando o loop terminar, retorne a. Ele é o primeiro nó compartilhado ou -1.

def getIntersectionNode(next, headA, headB):
    a, b = headA, headB
    # Each pointer walks its own list, then the other one. Both cover
    # the same number of nodes, so they reach the meeting node together,
    # or reach -1 together when there is none.
    while a != b:
        a = headB if a == -1 else next[a]
        b = headA if b == -1 else next[b]
    return a

Armadilhas e casos extremos

Ir do último nó direto para a outra cabeça, pulando a parada em -1. Quando as listas não têm nenhum elemento em comum, os ponteiros nunca assumem o mesmo valor e o loop é executado para sempre.
Reiniciar um ponteiro na própria cabeça. Cada ponteiro então percorre sua própria lista, e eles só se encontram quando as voltas coincidem, o que pode levar até (m + 1)·(k + 1) movimentos.
Tratar a ordem do array como a ordem da lista. O nó 0 é uma cabeça somente se headA ou headB indicar isso, e nós vizinhos no array não são vizinhos em uma lista.
Em Lua e R, esquecer que os arrays começam em 1. Mantenha os índices dos nós começando em 0 e leia next[node + 1].

Perguntas frequentes3

Como encontrar o ponto de interseção entre duas listas encadeadas sem usar memória extra?

Use dois ponteiros. Cada um percorre sua própria lista e, depois de passar do fim, continua a partir do início da outra lista. Ambos percorrem a mesma distância total, então chegam ao primeiro nó compartilhado ao mesmo tempo ou chegam juntos ao fim, caso não haja nenhum.

Você consegue encontrar a interseção comparando os comprimentos das listas?

Sim. Conte os nós das duas listas, avance o ponteiro da lista mais longa pela diferença e, em seguida, avance ambos um passo de cada vez até que sejam iguais. Isso também leva tempo O(m + k) e usa memória O(1); o método de alternância obtém o mesmo alinhamento sem as duas passagens de contagem.

Qual é a complexidade de tempo para encontrar a interseção de duas listas encadeadas?

Os métodos dos dois ponteiros e dos comprimentos são executados em O(m + k) tempo, com O(1) de memória extra. Armazenar uma lista em um conjunto ou em um vetor de marcações também é linear, mas requer memória para essa lista. Comparar cada par de nós leva O(m·k).

def getIntersectionNode(next, headA, headB):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

next = [-1, 4, 1, 5, 0, 1]
headA = 3
headB = 2

Saída Esperada

Intersection of Two Linked Lists

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada nó de A em relação a todos os nós de B

Marque os nós da lista B

Dois ponteiros que alternam entre listas

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos