GUÍA 07-10-26 Estructuras de Datos

CN122 · miércoles 07/10/2026 · 13:00-14:15 · Sesión 17

Taller de listas ligadas · Operaciones compuestas

SESIÓN DE CONSOLIDACIÓN

Problemas que combinan inserción, búsqueda y eliminación, que es donde de verdad se detectan los errores de manejo de apuntadores.

INVERTIR UNA LISTA

Con tres apuntadores —anterior, actual y siguiente— se recorre una sola vez invirtiendo cada enlace. Es O(n) en tiempo y O(1) en espacio, y es la pregunta de entrevista técnica más frecuente que existe.

• while (act) { sig = act->sig; act->sig = ant; ant = act; act = sig; } cabeza = ant;

MEZCLAR DOS LISTAS ORDENADAS

Se recorren en paralelo tomando siempre el menor. El resultado queda ordenado en O(n+m) sin memoria adicional si se reutilizan los nodos. Es el núcleo del merge sort, que veremos en las últimas semanas.

OTRAS OPERACIONES TÍPICAS

• Eliminar duplicados de una lista ordenada.
• Encontrar el k-ésimo desde el final con dos apuntadores separados k posiciones.
• Partir una lista en dos por su punto medio.
• Concatenar dos listas.

CÓMO DEPURAR APUNTADORES

• Dibujar la lista antes y después de cada operación; los errores se ven en el papel antes que en el código.
• Imprimir la lista completa después de cada paso mientras desarrollas.
• Probar siempre los tres casos frontera: lista vacía, un solo nodo, y operar sobre el primero y el último.

PRÁCTICA

Resolver los cinco problemas anteriores y probarlos con los casos frontera.