Dónde se unen dos cadenas
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
Guardar cada nodo de una lista en un conjunto y recorrer la otra funciona, pero cuesta O(n) de espacio. ¿Qué tienen en común los dos recorridos si los alineas?
Una vez que las listas se juntan, sus colas son idénticas. El único problema es que las dos cabezas están a distancias distintas del punto de unión.
Recorre cada lista con un puntero. Cuando uno llegue al final, haz que vuelva a empezar en la cabeza de la otra lista. Después de que ambos recorran a + b nodos, llegan juntos al nodo de unión, o juntos a None si no lo hay.
- Tiempo objetivo
- O(m + n)
- Espacio objetivo
- O(1)
Restricciones
- each list has at most 30,000 nodes
Solución
Supongamos que la lista a tiene x nodos antes de la unión, la lista b tiene y, y la cola compartida tiene z. Un puntero que recorre a y luego pasa a b cubre x + z + y nodos antes de llegar al nodo de unión, y un puntero que recorre b y luego a cubre y + z + x, la misma distancia, así que caen sobre él en el mismo paso. Cuando las listas nunca se encuentran, ambos punteros terminan la longitud combinada juntos y son None al mismo tiempo, lo que también termina el bucle. Cada puntero da como máximo a + b pasos, así que el tiempo es O(a + b) y el espacio extra es 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) # -> 7¿Lo que te frena es la idea y no el código? Recorrido y búsqueda lo explica.