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?
