Saltar al contenido

Dónde se unen dos cadenas

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

La misión

Problema

Dos historiales de versiones se guardan como listas simplemente enlazadas que pueden juntarse en un commit compartido y seguir juntas desde ahí hasta el final. Dadas las cabezas de ambas listas, devuelve el primer nodo que comparten, o None si nunca se encuentran. Compartido significa el mismo objeto nodo, no solo un valor igual. No cambies ninguna de las dos listas y usa solo O(1) de espacio extra. Cada lista tiene hasta 30 000 nodos.

Ejemplos

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é: el 1 que va antes es un nodo distinto en cada lista; solo coincide el valor
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é: caso límite: las listas comparten todo, así que la respuesta es la propia cabeza

Pistas

0 / 3

Tiempo objetivo
O(m + n)
Espacio objetivo
O(1)

Restricciones

  • each list has at most 30,000 nodes

¿Lo que te frena es la idea y no el código? Recorrido y búsqueda lo explica.

Python 3Ctrl+Enter ejecuta