El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios con Listas

Siguiente ►
►

Ha llegado la hora de convertir lo aprendido en oficio. Esta lección no introduce teoría nueva: es una sesión completa de entrenamiento con seis ejercicios progresivos que integran todo el módulo — desde manipular nodos sueltos hasta montar piezas reales del tablero de TaskFlow con operaciones combinadas. Varios de ellos (invertir una lista enlazada, detectar ciclos con dos punteros, fusionar listas ordenadas) son además clásicos absolutos de entrevista técnica: dominarlos no es solo aprobar este módulo, es preparación profesional directa. Trabaja cada ejercicio en tres pasos: dibuja los nodos y flechas en papel, escribe el código sin mirar la solución, y pruébalo con listas de 0, 1, 2 y varios elementos. Solo entonces compara con la solución comentada.

Contenido

  1. Material de partida: las clases del módulo
  2. Ejercicio 1 — Contar y extraer con nodos sueltos (calentamiento)
  3. Ejercicio 2 — Invertir una lista enlazada en el sitio
  4. Ejercicio 3 — Detectar un ciclo con dos punteros (liebre y tortuga)
  5. Ejercicio 4 — Fusionar dos tableros ordenados por prioridad
  6. Ejercicio 5 — Mover una tarea de posición en el tablero
  7. Ejercicio 6 — Historial navegable completo con lista doble

Material de partida: las clases del módulo

Todos los ejercicios reutilizan las clases construidas en las lecciones anteriores; cópialas en tu fichero de trabajo tal como quedaron:

  • Nodo y ListaEnlazada (lección 02-02): cabeza, cola, tamano, con insertar_al_inicio, insertar_al_final, borrar, buscar, __iter__, __len__, __str__.
  • NodoDoble y ListaDoblementeEnlazada (lección 02-03): con insertar_al_final, borrar_nodo, buscar_nodo, __iter__, __reversed__.
  • La tarea de TaskFlow sigue siendo el dict de siempre: {"id": ..., "titulo": ..., "prioridad": ..., "estado": ...}.

Función auxiliar para fabricar tableros de prueba rápidamente:

def tablero_de(*titulos_prioridades):
    """Crea una ListaEnlazada de tareas: tablero_de(("Logo", 2), ("Hotfix", 1))."""
    tablero = ListaEnlazada()
    for i, (titulo, prioridad) in enumerate(titulos_prioridades, start=1):
        tablero.insertar_al_final({"id": i, "titulo": titulo,
                                   "prioridad": prioridad, "estado": "pendiente"})
    return tablero

Errores Comunes y Consejos

Antes de empezar, los tropiezos que más veces verás en estos seis ejercicios concretos:

  • Perder la referencia al resto de la lista al recablear (sobre todo en el ejercicio 2): en cuanto reasignas siguiente sin haber guardado antes a dónde apuntaba, la cola de la lista se esfuma. La solución universal es una variable temporal que "sujete" lo que vas a soltar.
  • Descuidar cabeza, cola y tamano al operar con nodos por tu cuenta: si inviertes o mueves nodos manipulando flechas, las referencias estratégicas de la clase deben quedar coherentes al final, o el siguiente insertar_al_final corromperá la lista.
  • Probar solo el caso bonito. Lista vacía, un nodo, dos nodos, el elemento en la cabeza, el elemento en la cola: cada ejercicio indica sus fronteras y las soluciones las tratan explícitamente. Un algoritmo de listas que no has probado en las fronteras no está terminado.
  • Comparar nodos con == donde toca is (ejercicio 3 especialmente): identidad y igualdad no son lo mismo, y con tareas-dict duplicadas la diferencia es un fallo real.
  • Consejo general: en los ejercicios de recableado (2, 4 y 5), escribe primero en papel la secuencia numerada de asignaciones y valida sobre el dibujo que ninguna flecha necesaria se pierde antes de ser copiada. Es el método de las lecciones anteriores, y aquí es donde rinde.

Ejercicios

Ejercicio 1 — Contar y extraer con nodos sueltos (calentamiento). Sin usar ListaEnlazada (solo la clase Nodo y una variable cabeza), escribe dos funciones: (a) contar_estado(cabeza, estado), que devuelva cuántas tareas de la cadena tienen ese estado; (b) extraer_completadas(cabeza), que elimine de la cadena todas las tareas con estado "completada" y devuelva la nueva cabeza (ojo: las completadas pueden estar al principio, en medio, al final... o ser todas). Fronteras: cadena vacía y cadena donde todo se elimina.

Ejercicio 2 — Invertir una lista enlazada en el sitio. Escribe un método invertir() para ListaEnlazada que invierta el orden de los nodos sin crear nodos nuevos ni estructuras auxiliares: solo redirigiendo flechas siguiente. El tablero A -> B -> C debe quedar C -> B -> A, con cabeza, cola y el recorrido coherentes. Coste exigido: O(n) en tiempo y O(1) en espacio extra. Pista: recorre con tres referencias (previo, actual, posterior). En TaskFlow: ver el tablero "de las últimas a las primeras" sin construir una copia.

Ejercicio 3 — Detectar un ciclo con dos punteros (liebre y tortuga). Un fallo al programar una lista circular (lección 02-04) puede dejar un ciclo accidental en un tablero que debería ser lineal: el recorrido nunca termina. Escribe tiene_ciclo(cabeza) que devuelva True/False usando el algoritmo de Floyd: dos punteros que avanzan a la vez, uno de salto en salto (tortuga) y otro de dos en dos (liebre); si hay ciclo, la liebre acabará alcanzando a la tortuga; si no, la liebre llegará a None. Prohibido usar memoria auxiliar proporcional a la lista (nada de guardar los nodos visitados en un set). Explica en un comentario por qué el algoritmo termina siempre.

Ejercicio 4 — Fusionar dos tableros ordenados por prioridad. Dos equipos fusionan sus proyectos. Cada tablero es una ListaEnlazada ya ordenada por prioridad ascendente (gracias al insertar_ordenado del ejercicio 2 de la lección 02-02). Escribe fusionar(tablero_a, tablero_b) que devuelva una nueva ListaEnlazada ordenada con todas las tareas, reutilizando los nodos existentes (sin crear nodos nuevos: solo recableando), en O(n + m). A igualdad de prioridad, las tareas del tablero A van antes. Fronteras: uno o ambos tableros vacíos. Nota: los tableros originales quedan vacíos tras la fusión (sus nodos ahora pertenecen al resultado); deja sus cabeza/cola/tamano a cero para que no queden corruptos.

Ejercicio 5 — Mover una tarea de posición en el tablero. El usuario arrastra una tarea a otra posición del tablero (la operación estrella de cualquier gestor de tareas). Escribe un método mover(self, id_tarea, nueva_posicion) para ListaEnlazada que localice la tarea por id, la desenganche y la reinserte en la posición indicada (0 = principio), reutilizando el nodo (sin crear uno nuevo), y devuelva True si existía o False si no. Cuida: mover a la misma posición, mover a la cabeza, mover a la cola, id inexistente, y que cabeza/cola/tamano queden coherentes. ¿Cuál es el coste?

Ejercicio 6 — Historial navegable completo con lista doble. Completa el HistorialTareas de la lección 02-03 con el comportamiento real de un navegador: cuando el usuario está en mitad del historial (tras pulsar "atrás") y visita una tarea nueva, todas las tareas que quedaban "adelante" se descartan — la nueva visita se convierte en el final del historial. Añade también donde_estoy() (tarea actual o None) y recorrido() (lista de títulos de todo el historial marcando con * la posición actual). Usa ListaDoblementeEnlazada y borra los nodos descartados de verdad (con borrar_nodo), manteniendo tamano correcto. Demuestra la secuencia: visitar T1, T2, T3, atrás, atrás, visitar T4 → el historial debe ser T1, T4.

Soluciones

Solución 1:

def contar_estado(cabeza, estado):
    """Recorrido clásico con contador. Coste: O(n)."""
    contador = 0
    actual = cabeza
    while actual is not None:
        if actual.dato["estado"] == estado:
            contador += 1
        actual = actual.siguiente
    return contador

def extraer_completadas(cabeza):
    """Elimina todas las tareas completadas. Devuelve la nueva cabeza. Coste: O(n)."""
    # Fase 1: avanzar la cabeza mientras las primeras estén completadas
    while cabeza is not None and cabeza.dato["estado"] == "completada":
        cabeza = cabeza.siguiente        # la antigua cabeza queda sin referencias
    # Fase 2: puentear las completadas interiores con el patrón anterior/actual
    anterior = cabeza
    while anterior is not None and anterior.siguiente is not None:
        if anterior.siguiente.dato["estado"] == "completada":
            anterior.siguiente = anterior.siguiente.siguiente   # puente
            # (no avanzamos: el nuevo siguiente podría estar también completada)
        else:
            anterior = anterior.siguiente
    return cabeza

Comentarios: la fase 1 resuelve el caso "completadas al principio" (incluido "todas completadas", que devuelve None, la cadena vacía). En la fase 2, el detalle fino es no avanzar tras puentear: si dos completadas van seguidas, el nuevo anterior.siguiente también debe examinarse. Es el error más frecuente de este ejercicio: quien avanza siempre, se salta una de cada dos completadas consecutivas.

Solución 2:

    def invertir(self):
        """Invierte la lista redirigiendo flechas. O(n) tiempo, O(1) espacio."""
        previo = None
        actual = self.cabeza
        self.cola = self.cabeza          # la antigua cabeza será la nueva cola
        while actual is not None:
            posterior = actual.siguiente # 1: sujetar el resto antes de soltar
            actual.siguiente = previo    # 2: dar la vuelta a la flecha
            previo = actual              # 3: avanzar previo...
            actual = posterior           # 4: ...y actual
        self.cabeza = previo             # el último visitado es la nueva cabeza

El corazón es el cuarteto del bucle, siempre en ese orden. La línea 1 es la variable temporal que "sujeta" el resto de la lista: sin ella, la línea 2 destruiría el único camino hacia delante. Traza a mano con A -> B -> C:

graph LR
    subgraph "Tras la primera iteración"
    A["A"] -- "flecha invertida" --> N["None"]
    B["B (actual)"] --> C["C"]
    P["previo"] --> A
    end

Cada iteración da la vuelta a exactamente una flecha; al agotarse actual, previo sostiene la antigua última, que pasa a ser cabeza. Fronteras: con lista vacía el bucle no ejecuta y cabeza/cola quedan None; con un nodo, la flecha A -> None "se invierte" a sí misma sin cambios. Verifica con print(tablero) antes y después.

Solución 3:

def tiene_ciclo(cabeza):
    """Algoritmo de Floyd (liebre y tortuga). O(n) tiempo, O(1) espacio."""
    tortuga = cabeza
    liebre = cabeza
    while liebre is not None and liebre.siguiente is not None:
        tortuga = tortuga.siguiente            # avanza 1
        liebre = liebre.siguiente.siguiente    # avanza 2
        if tortuga is liebre:                  # ¡identidad, no igualdad!
            return True
    return False
    # ¿Por qué termina siempre? Si no hay ciclo, la liebre encuentra None en
    # a lo sumo n/2 pasos. Si lo hay, ambos punteros acaban dentro del ciclo,
    # y la distancia liebre-tortuga se REDUCE EN 1 en cada paso (la liebre
    # recorta 2−1=1 por iteración sobre un anillo finito), luego llega a 0:
    # se encuentran, sin que la liebre pueda "saltar por encima".

Detalles imprescindibles: la condición del while comprueba liebre y liebre.siguiente antes del doble salto (si no, AttributeError al final de una lista sin ciclo); la comparación es is porque buscamos el mismo nodo — dos tareas con datos idénticos no son un ciclo. Prueba de fuego:

tablero = tablero_de(("Logo", 2), ("Servidor", 2), ("Hotfix", 1))
print(tiene_ciclo(tablero.cabeza))     # False
tablero.cola.siguiente = tablero.cabeza.siguiente   # sabotaje: creamos un ciclo
print(tiene_ciclo(tablero.cabeza))     # True
# (deshacer el sabotaje antes de seguir usando el tablero)
tablero.cola.siguiente = None

La alternativa "apuntar los nodos visitados en un set" también es O(n) en tiempo, pero gasta O(n) memoria; Floyd logra lo mismo con dos referencias. Es el ejemplo canónico de intercambio tiempo-memoria resuelto con ingenio, y pregunta recurrente de entrevista.

Solución 4:

def fusionar(tablero_a, tablero_b):
    """Fusiona dos listas ordenadas por prioridad reutilizando nodos. O(n+m)."""
    resultado = ListaEnlazada()
    a = tablero_a.cabeza
    b = tablero_b.cabeza

    def enganchar(nodo):
        """Añade un nodo existente al final del resultado (recableo puro)."""
        nodo.siguiente = None
        if resultado.cabeza is None:
            resultado.cabeza = nodo
        else:
            resultado.cola.siguiente = nodo
        resultado.cola = nodo
        resultado.tamano += 1

    while a is not None and b is not None:
        if a.dato["prioridad"] <= b.dato["prioridad"]:   # <=: empate gana A
            siguiente = a.siguiente     # sujetar antes de recablear
            enganchar(a)
            a = siguiente
        else:
            siguiente = b.siguiente
            enganchar(b)
            b = siguiente

    resto = a if a is not None else b   # una de las dos se agotó:
    while resto is not None:            # el resto entra en bloque, ya ordenado
        siguiente = resto.siguiente
        enganchar(resto)
        resto = siguiente

    # Los originales ceden sus nodos: dejarlos vacíos y coherentes
    tablero_a.cabeza = tablero_a.cola = None
    tablero_a.tamano = 0
    tablero_b.cabeza = tablero_b.cola = None
    tablero_b.tamano = 0
    return resultado

Claves: en cada vuelta se compara solo la pareja de frentes y se engancha la menor — por eso el total es O(n + m), cada nodo se toca una vez. El <= (y no <) da la estabilidad pedida: en empate entra primero la de A. enganchar es un mini-insertar_al_final que recibe un nodo en lugar de crear uno: ahí está el "reutilizar sin crear". Y el vaciado final de los originales evita el error de las dos listas compartiendo nodos: si tablero_a conservara su cabeza, modificar el resultado corrompería también a A. Prueba: fusionar(tablero_de(("Hotfix", 1), ("Logo", 2)), tablero_de(("Caída BD", 1), ("Docs", 3))) → Hotfix(A), Caída BD(B), Logo, Docs.

Solución 5:

    def mover(self, id_tarea, nueva_posicion):
        """Desengancha la tarea por id y la reinserta en nueva_posicion. O(n)."""
        # Fase 1: localizar y desenganchar (patrón anterior/actual de 02-02)
        anterior = None
        actual = self.cabeza
        while actual is not None and actual.dato["id"] != id_tarea:
            anterior = actual
            actual = actual.siguiente
        if actual is None:
            return False                       # id inexistente
        if anterior is None:
            self.cabeza = actual.siguiente     # era la cabeza
        else:
            anterior.siguiente = actual.siguiente
        if actual is self.cola:
            self.cola = anterior               # era la cola
        self.tamano -= 1
        actual.siguiente = None                # nodo suelto y limpio

        # Fase 2: reinsertar el MISMO nodo en la posición pedida
        if nueva_posicion <= 0 or self.cabeza is None:
            actual.siguiente = self.cabeza     # mini insertar_al_inicio con nodo
            self.cabeza = actual
            if self.cola is None:
                self.cola = actual
        elif nueva_posicion >= self.tamano:
            self.cola.siguiente = actual       # mini insertar_al_final con nodo
            self.cola = actual
        else:
            previo = self.cabeza
            for _ in range(nueva_posicion - 1):
                previo = previo.siguiente
            actual.siguiente = previo.siguiente
            previo.siguiente = actual
        self.tamano += 1
        return True

Estructura en dos fases limpias: desenganchar (que es el borrar de 02-02 conservando el nodo en vez de soltarlo) y reinsertar (que es insertar_en recibiendo un nodo en vez de un dato). El matiz sutil: la posición se interpreta sobre la lista ya sin la tarea — mover a la misma posición funciona sin caso especial, porque desenganchar y reinsertar en el mismo sitio es idempotente. Coste O(n): una pasada para localizar más otra parcial para situarse; el recableado, como siempre, O(1). Prueba las cuatro fronteras del enunciado con un tablero de 4 tareas e imprime el tablero y len tras cada una.

Solución 6:

class HistorialTareas:
    """Historial de navegación completo sobre lista doble (TaskFlow)."""
    def __init__(self):
        self.lista = ListaDoblementeEnlazada()
        self.actual = None            # nodo de la posición actual

    def visitar(self, tarea):
        """Nueva visita: descarta el 'adelante' y añade al final. O(k) descartados."""
        # Descartar todo lo que había después de la posición actual
        if self.actual is not None:
            while self.actual.siguiente is not None:
                self.lista.borrar_nodo(self.actual.siguiente)   # O(1) cada uno
        self.lista.insertar_al_final(tarea)
        self.actual = self.lista.cola

    def atras(self):
        if self.actual is not None and self.actual.anterior is not None:
            self.actual = self.actual.anterior
        return self.donde_estoy()

    def adelante(self):
        if self.actual is not None and self.actual.siguiente is not None:
            self.actual = self.actual.siguiente
        return self.donde_estoy()

    def donde_estoy(self):
        return self.actual.dato if self.actual is not None else None

    def recorrido(self):
        """Títulos del historial, marcando la posición actual con *."""
        marcas = []
        nodo = self.lista.cabeza
        while nodo is not None:
            titulo = nodo.dato["titulo"]
            marcas.append(f"*{titulo}*" if nodo is self.actual else titulo)
            nodo = nodo.siguiente
        return marcas


# Demostración de la secuencia pedida:
def tarea(i):
    return {"id": i, "titulo": f"T{i}", "prioridad": 2, "estado": "en curso"}

h = HistorialTareas()
h.visitar(tarea(1)); h.visitar(tarea(2)); h.visitar(tarea(3))
print(h.recorrido())        # ['T1', 'T2', '*T3*']
h.atras(); h.atras()
print(h.recorrido())        # ['*T1*', 'T2', 'T3']
h.visitar(tarea(4))
print(h.recorrido())        # ['T1', '*T4*']  ← T2 y T3 descartadas
print(len(h.lista))         # 2

Todo el módulo trabaja junto en esta clase: el descarte usa borrar_nodo — O(1) por nodo porque tenemos la referencia, la moraleja de 02-03 —, siempre sobre self.actual.siguiente (que se va "reenganchando" solo gracias a los puentes del borrado, sin índices ni búsquedas); atras/adelante son movimientos O(1) por las flechas; y recorrido compara nodos con is para marcar la posición. Es, a pequeña escala, el mismo diseño del historial de Chrome o Firefox: cuando navegas desde mitad del historial, el futuro descartado no vuelve.

Conclusión

Seis ejercicios y todo el módulo en juego: el patrón anterior/actual y los puentes (ejercicio 1), la inversión en el sitio con su cuarteto de asignaciones (2), la liebre y la tortuga de Floyd como detector de ciclos en O(1) de memoria (3), la fusión ordenada reutilizando nodos en O(n + m) (4), el mover-tarea que combina desenganchar y reinsertar (5) y el historial de navegador donde los borrados O(1) de la lista doble rinden de verdad (6). Si has llegado hasta aquí resolviéndolos —y probándolos en sus fronteras—, las listas enlazadas ya no son teoría: son herramienta. Con el módulo 2 completo, TaskFlow tiene tablero, reparto de turnos e historial, y tú tienes el vocabulario de nodos, flechas y recableados sobre el que se construye casi todo lo que viene. En el módulo 3 lo estrenamos: la pila, la estructura de "el último en entrar es el primero en salir", que podrás implementar en unas pocas líneas... precisamente porque ya sabes insertar y borrar por la cabeza de una lista enlazada en O(1). El deshacer de TaskFlow te está esperando.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados