Supongamos que hay dos listas enlazadas individualmente, las cuales se cruzan en algún punto y se convierten en una sola lista enlazada. Se conocen los punteros de cabecera o de inicio de ambas listas, pero se desconocen el Node de intersección y las longitudes de las listas.
¿Cuál es la complejidad del tiempo en el peor de los casos del algoritmo óptimo para encontrar el Node que se cruza a partir de dos listas enlazadas que se cruzan?
(A) Θ(n*m), donde m, n son longitudes de listas dadas
(B) Θ(n^2), donde m>n y m, n son longitudes de listas dadas
(C) Θ(m+n ), donde m, n son longitudes de listas dadas
(D) Θ(min(n, m)), donde m, n son longitudes de listas dadas
Respuesta: (C)
Explicación:Esto toma un tiempo Θ(m+n) y un espacio O(1) en el peor de los casos, donde M y N son la longitud total de las listas enlazadas.
- Recorra las dos listas enlazadas para encontrar m y n.
- Vuelva a las cabezas, luego atraviese |m − n| Nodes en la lista más larga.
- Ahora camine al unísono y compare los Nodes hasta encontrar los comunes.
La opción (C) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA