Pular para o conteúdo

Onde duas cadeias se juntam

Fácil#two-pointers#list-traversal~15 min

A missão

Problema

Dois históricos de versões são guardados como listas simplesmente encadeadas que podem se juntar em um commit compartilhado e seguir juntas dali até o fim. Dados os heads das duas listas, retorne o primeiro nó que elas compartilham, ou None se elas nunca se encontrarem. Compartilhado significa o mesmo objeto de nó, não apenas um valor igual. Não altere nenhuma das listas e use só O(1) de espaço extra. Cada lista tem até 30.000 nós.

Exemplos

Input:  a = 4 -> 1 -> 8 -> 4 -> 5, b = 5 -> 6 -> 1 -> 8 -> 4 -> 5,
        both lists share the nodes 8 -> 4 -> 5
Output: the node holding 8
Por quê: o 1 antes dele é um nó diferente em cada lista; só o valor coincide
Input:  a = 2 -> 6 -> 4, b = 1 -> 5, no shared nodes
Output: None
Input:  a = 7, b = 7, where both heads are the same node
Output: the node holding 7
Por quê: edge case: as listas compartilham tudo, então a resposta é o próprio head

Dicas

0 / 3

Tempo-alvo
O(m + n)
Espaço-alvo
O(1)

Restrições

  • each list has at most 30,000 nodes

Travou na ideia, e não no código? Percurso e busca explica isso.

Python 3Ctrl+Enter executa