Onde duas cadeias se juntam
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
Guardar todos os nós de uma lista em um conjunto (set) e percorrer a outra funciona, mas custa O(n) de espaço. O que os dois percursos têm em comum se você os alinhar?
Depois que as listas se juntam, os seus trechos finais são idênticos. O único problema é que os dois heads ficam a distâncias diferentes do ponto de junção.
Percorra cada lista com um ponteiro. Quando um deles chegar ao fim, recomece-o no head da outra lista. Depois de os dois percorrerem a + b nós, eles chegam juntos ao nó de junção, ou juntos a None, se não houver um.
- Tempo-alvo
- O(m + n)
- Espaço-alvo
- O(1)
Restrições
- each list has at most 30,000 nodes
Solução
Digamos que a lista a tenha x nós antes da junção, a lista b tenha y e o trecho final compartilhado tenha z. Um ponteiro que percorre a e depois passa para b cobre x + z + y nós antes de chegar ao nó de junção, e um ponteiro que percorre b e depois a cobre y + z + x, a mesma distância, então os dois caem nele no mesmo passo. Quando as listas nunca se encontram, os dois ponteiros terminam o comprimento combinado juntos e ficam None ao mesmo tempo, o que também encerra o loop. Cada ponteiro dá no máximo a + b passos, então o tempo é O(a + b), e o espaço extra é O(1).
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def merge_point(a, b):
p, q = a, b
while p is not q:
p = p.next if p else b # switch to the other list at the end
q = q.next if q else a
return p # the shared node, or None
shared = Node(8, Node(4, Node(5)))
first_a = Node(4, Node(1, shared))
first_b = Node(5, Node(6, Node(1, shared)))
print(merge_point(first_a, first_b).val) # -> 8
print(merge_point(Node(2, Node(6, Node(4))), Node(1, Node(5)))) # -> None
same = Node(7)
print(merge_point(same, same).val) # -> 7Travou na ideia, e não no código? Percurso e busca explica isso.