18 votos

Encontrar el nodo que se intersecta a partir de dos listas vinculadas que se intersectan

Supongamos que hay dos listas unidas que se intersectan en algún momento y se convierten en una sola lista unida.

Se conocen los puntos de partida y de llegada de ambas listas, pero no se conoce el nodo de intersección. Además, se desconoce el número de nodos de cada una de las listas antes de que se crucen y ambas listas pueden tenerlo diferente, es decir, la Lista 1 puede tener nodos antes de llegar al punto de intersección y la Lista 2 puede tener nodos m antes de llegar al punto de intersección donde m y n pueden estar

  • m = n,
  • m < n o
  • m > n

Una solución conocida o fácil es comparar cada puntero de nodo de la primera lista con todos los demás punteros de nodo de la segunda lista por la que los punteros de nodo que coincidan nos llevarán al nodo que se intersecta. Pero, la complejidad del tiempo en este caso O(n) 2 ) que será alto.

¿Cuál es la forma más eficiente de encontrar el nodo de intersección?

30voto

KennyTM Puntos 232647

Esto toma O(M+N) tiempo y O(1) espacio, donde M y N son la longitud total de las listas enlazadas. Tal vez sea ineficiente si la parte común es muy larga (es decir, M,N >> m,n)

  1. Recorra las dos listas enlazadas para encontrar M y N.
  2. Vuelve a las cabezas, luego atraviesa los nodos M - N de la lista más larga.
  3. Ahora camina al paso de la cerradura y compara los nodos hasta que encuentres los comunes.

Editar: Ver http://richardhartersworld.com/cri/2008/linkedlist.html

12voto

Jakob Borg Puntos 10869

Si es posible, podrías añadir un campo de "color" o similar a los nodos. Iterar sobre una de las listas, coloreando los nodos sobre la marcha. Luego itera sobre la segunda lista. Tan pronto como llegues a un nodo que ya esté coloreado, habrás encontrado la intersección.

5voto

ddyer Puntos 1546

Vierte el contenido (o la dirección) de ambas listas en una tabla de hash. La primera colisión es tu intersección.

3voto

Farm Puntos 635

Revisa los últimos nodos de cada lista, si hay una intersección su último nodo será el mismo.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X