Intersection of Two Linked Lists

+10

Dos listas simplemente enlazadas están en un mismo conjunto de nodos. El nodo i enlaza con el nodo next[i], y -1 marca el final de una lista. La lista A empieza en el nodo headA y la lista B, en el nodo headB. Los nodos no están almacenados en ningún orden particular, así que sigue los enlaces.

Las dos listas pueden encontrarse: a partir de cierto nodo, continúan por los mismos nodos hasta el final. Devuelve el índice del primer nodo que aparece en ambas listas, o -1 si no comparten ningún nodo.

Función

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

nextinteger-array: el índice del nodo al que enlaza cada nodo, o -1 para el último nodo de una lista
headAinteger: el primer nodo de la lista A
headBinteger: el primer nodo de la lista B
Devuelveinteger: el primer nodo que comparten las dos listas, o -1

Restricciones

2 ≤ n ≤ 10⁴, donde n es la longitud de next.
Cada next[i] es -1 o un índice de nodo entre 0 y n-1.
0 ≤ headA, headB ≤ n-1 y headA ≠ headB.
Ambas listas terminan en -1 sin visitar un nodo dos veces. No hay ningún ciclo.
Cada nodo está en la lista A, en la lista B o en ambas.

Ejemplos

Entrada: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Salida: 1
Explicación: A visita 3, 5, 1, 4, 0 y B visita 2, 1, 4, 0. A partir del nodo 1, comparten todos los nodos, y ningún nodo anterior de A está en B, así que la respuesta es 1.

Entrada: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Salida: -1
Explicación: La lista A es 0, 2, 4 y la lista B es 1, 3. Ambas terminan en -1 sin tocar un nodo común, así que la respuesta es -1.

Entrada: next = [3, 2, 0, -1]headA = 1headB = 0
Salida: 0
Explicación: La lista A es 1, 2, 0, 3 y la lista B es 0, 3. La lista B es la cola de la lista A, así que el primer nodo compartido es headB mismo, el nodo 0.

Para ir más allá

¿Puedes encontrar el nodo en tiempo O(m + k) con memoria adicional O(1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un nodo tiene un next, así que dos listas que se encuentran nunca vuelven a separarse. Forman una Y: dos inicios separados que se unen a una cola compartida, y la respuesta es el punto de unión. Los inicios pueden tener longitudes distintas, así que avanzar por ambas listas a la vez hace que se pase por alto el punto de unión. Abajo, m y k son las longitudes de A y B.

Compara cada nodo de A con todos los de B

Correcto, pero no termina con las pruebas más grandes

Intuición

Un puntero es un índice de nodo, y avanzar es node = next[node]. Para cada nodo a de A, en orden, recorre todo B y compara cada nodo con a. El primer a que coincide es la respuesta, porque todos los nodos anteriores de A ya fallaron. Vuelve a recorrer B por cada nodo de A: con 5000 nodos en cada lista y ningún nodo compartido, eso supone 2.5 × 10^7 comparaciones.

Algoritmo

Asigna a = headA.
Mientras a no sea -1, recorre b desde headB hasta -1.
Si b == a en algún momento, devuelve a.
De lo contrario, avanza a a = next[a] y repite.
Si la lista A se agota, devuelve -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

Marca los nodos de la lista B

Intuición

Responde «¿está este nodo en B?» una vez por cada nodo: recorre B y marca cada nodo en un arreglo booleano de tamaño n. Los índices de los nodos son enteros pequeños, así que un arreglo sirve como conjunto hash. Luego recorre A desde su cabeza. El primer nodo marcado está en ambas listas, y es el primero de ellos porque recorres A en orden. En el primer ejemplo, B marca 2, 1, 4, 0, y el recorrido por A pasa por 3 y 5 antes de detenerse en 1. Cada lista se recorre una vez, así que el tiempo es O(m + k), a costa de n marcas.

Algoritmo

Crea onB, un arreglo de n valores booleanos establecidos en false.
Recorre la lista B desde headB y establece onB[node] = true para cada nodo.
Recorre la lista A desde headA. Devuelve el primer nodo con onB[node] en true.
Si la lista A termina, devuelve -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

Dos punteros que cambian de lista

Intuición

Divide cada lista en el punto de unión: A tiene x nodos privados y después los c compartidos, y B tiene y nodos privados y después los mismos c. El puntero a recorre A, pasa por -1, después se reinicia en headB y llega al punto de unión por segunda vez tras x + c + 1 + y movimientos. El puntero b recorre B y después A, y llega tras y + c + 1 + x movimientos. Los totales coinciden. En el primer ejemplo, x = 2, y = 1 y c = 3, y ambos quedan en el nodo 1 tras siete movimientos.

Si no hay una cola compartida, ambos punteros quedan en -1 tras m + 1 + k movimientos (tras m cuando m = k), y el bucle devuelve -1. Esa parada común explica por qué cada puntero pasa por -1 antes de cambiar de lista. Cada puntero se mueve como máximo m + k + 1 veces, con dos índices de memoria.

Algoritmo

Establece a = headA y b = headB.
Mientras a != b: mueve a a headB si es -1; de lo contrario, a next[a].
En la misma ronda, mueve b a headA si es -1; de lo contrario, a next[b].
Cuando termine el bucle, devuelve a. Es el primer nodo compartido o -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

Errores comunes y casos límite

Pasar directamente del último nodo a la otra cabeza, saltándose la parada en -1. Cuando las listas no comparten ningún nodo, los punteros nunca tienen el mismo valor y el bucle se ejecuta para siempre.
Reiniciar un puntero en su propia cabeza. Entonces cada puntero recorre repetidamente su propia lista, y solo se encuentran cuando coinciden las vueltas, lo que puede requerir hasta (m + 1)·(k + 1) movimientos.
Tratar el orden del arreglo como el orden de la lista. El nodo 0 es una cabeza solo si headA o headB así lo indica, y los nodos adyacentes en el arreglo no son necesariamente adyacentes en una lista.
En Lua y R, olvidar que los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 y lee next[node + 1].

Preguntas frecuentes3

¿Cómo encuentras dónde se intersectan dos listas enlazadas sin memoria adicional?

Ejecuta dos punteros. Cada uno recorre su propia lista y, después de llegar al final, continúa desde la cabeza de la otra lista. Ambos recorren la misma distancia total, así que llegan al primer nodo compartido al mismo tiempo, o al final juntos si no hay ninguno.

¿Puedes encontrar la intersección comparando las longitudes de las listas?

Sí. Cuenta los nodos de ambas listas, adelanta el puntero de la lista más larga la diferencia, después avanza ambos un paso a la vez hasta que sean iguales. Esto también requiere un tiempo de O(m + k) y una memoria de O(1); el método de alternancia consigue la misma alineación sin las dos pasadas de conteo.

¿Cuál es la complejidad temporal de encontrar la intersección de dos listas enlazadas?

Los métodos de dos punteros y de longitudes se ejecutan en tiempo O(m + k) y usan O(1) de memoria adicional. Guardar una lista en un conjunto o en una matriz de marcas también es lineal, pero requiere memoria para esa lista. Comparar cada par de nodos lleva O(m·k).

def getIntersectionNode(next, headA, headB):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

Intersection of Two Linked Lists

Función

Restricciones

Ejemplos

Pistas

Solución

Compara cada nodo de A con todos los de B

Marca los nodos de la lista B

Dos punteros que cambian de lista

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares