LinkedList en Python — ejercicios para dominar las estructuras encadenadas
La LinkedList en Python ejercicios con solución cierran este bloque y con él el temario completo de FP2. Ya viste la teoría y practicaste con programas reales. Ahora toca resolver por tu cuenta. Tres ejercicios en tres niveles, todos con su diagrama, sus pistas y su solución comentada. El hilo conductor es siempre el mismo: los dos errores que más destrozan una implementación de LinkedList son modificar un puntero antes de guardar el siguiente, y olvidar los casos especiales de lista vacía o de un solo elemento.
Como siempre: intenta resolverlo, usa la pista si llevas más de 10 minutos atascado, pega tu código en pythontutor.com y compara con la solución comentada al final.
Partimos de la clase LinkedList completa del artículo de teoría.
Tabla de Contenidos
LinkedList en Python ejercicios — Nivel Básico
Ejercicio 1 — Obtener el elemento en la posición N
Añade a la clase LinkedList un método obtener(posicion) que devuelva el valor del elemento en la posición dada (empezando desde 0). Si la posición no existe, lanza IndexError.
La salida debe ser:
Lista: 10 → 20 → 30 → 40 → 50 → None lista.obtener(0) → 10 (primer elemento) lista.obtener(2) → 30 (tercero) lista.obtener(4) → 50 (último) lista.obtener(5) → IndexError: posición 5 fuera de rango (longitud 5) lista.obtener(-1) → IndexError: posición -1 fuera de rango (longitud 5)
El reto adicional: implementa también obtener_desde_final(posicion) que devuelva el elemento contando desde el final, posición 0 es el último, posición 1 el penúltimo, etc. Sin conocer la longitud de la lista y en un solo recorrido.
lista.obtener_desde_final(0) → 50 (último) lista.obtener_desde_final(1) → 40 (penúltimo) lista.obtener_desde_final(4) → 10 (primero)
💡 Pista — el error de olvidar casos especiales:
# MAL — no valida la posición
def obtener(self, posicion):
actual = self.__primero
for i in range(posicion):
actual = actual.siguiente # si posicion > longitud → AttributeError en None.siguiente
return actual.valor # si lista vacía → AttributeError en None.valor
# BIEN — valida primero
def obtener(self, posicion):
if posicion < 0 or posicion >= self.__longitud:
raise IndexError(f"posición {posicion} fuera de rango (longitud {self.__longitud})")
actual = self.__primero
for _ in range(posicion):
actual = actual.siguiente
return actual.valor
Para obtener_desde_final sin conocer la longitud, la técnica clásica usa dos punteros que avanzan a distinta velocidad, uno va N pasos por delante del otro:
Queremos el elemento en posición 1 desde el final (penúltimo) en lista: 10 → 20 → 30 → 40 → 50 → None Adelantamos el puntero rápido N+1 pasos: rapido avanza 2 pasos: apunta a [30] lento apunta a [10] Ahora avanzamos los dos juntos hasta que rápido llega a None: rapido=[30], lento=[10] → rapido=[40], lento=[20] rapido=[40], lento=[20] → rapido=[50], lento=[30] rapido=[50], lento=[30] → rapido=None, lento=[40] rapido=None → lento apunta al penúltimo → devolver lento.valor = 40 ✓
LinkedList en Python ejercicios — Nivel Intermedio
Ejercicio 2 — Eliminar duplicados de una LinkedList
Añade a la clase LinkedList un método eliminar_duplicados() que elimine todas las ocurrencias duplicadas dejando solo la primera aparición de cada valor. La lista original se modifica en su lugar.
La salida debe ser:
Lista original: 10 → 20 → 10 → 30 → 20 → 40 → 10 → None Después de eliminar_duplicados(): 10 → 20 → 30 → 40 → None Lista sin duplicados desde el principio: 5 → 8 → 3 → None Después de eliminar_duplicados(): 5 → 8 → 3 → None (no cambia) Lista con todos iguales: 7 → 7 → 7 → 7 → None Después de eliminar_duplicados(): 7 → None
La operación debe ser en el mismo lugar, sin crear una lista nueva. El método modifica self.
💡 Pistas:
El error de modificar primero antes de guardar siguiente aparece aquí de forma muy sutil. Cuando eliminas un nodo duplicado tienes que usar el patrón anterior / actual:
# MAL — pierdes el siguiente al duplicado
if actual.valor in vistos:
anterior.siguiente = actual.siguiente # ← bien hasta aquí
actual = actual.siguiente # ← también bien
# pero si no era duplicado:
anterior = actual # ← MAL: anterior NO debe avanzar cuando eliminas
actual = actual.siguiente
# BIEN — la clave está en cuándo avanzas anterior
if actual.valor in vistos:
anterior.siguiente = actual.siguiente # elimina el nodo
actual = actual.siguiente # avanza solo actual
# anterior NO avanza — sigue apuntando al mismo nodo
else:
vistos.add(actual.valor)
anterior = actual # avanza anterior solo si NO eliminaste
actual = actual.siguiente
El caso especial de lista vacía o de un solo elemento: si __primero es None o si no hay duplicados, el método debe funcionar sin hacer nada ni lanzar errores.
Para saber qué valores ya has visto usa un set, la estructura perfecta para comprobar pertenencia en O(1):
vistos = set() # si actual.valor in vistos → es duplicado → eliminar # si actual.valor not in vistos → primera vez → añadir a vistos
LinkedList en Python ejercicios — Desafío Final
Ejercicio 3 — Detectar si una LinkedList tiene un ciclo
Una LinkedList tiene un ciclo cuando uno de sus nodos apunta a un nodo anterior en vez de avanzar hacia None. Eso hace que la lista sea infinita, si intentas recorrerla con el patrón habitual nunca terminas.
Lista normal:
[10] → [20] → [30] → [40] → None
Lista con ciclo (el último apunta al segundo):
[10] → [20] → [30] → [40]
↑ |
└─────────┘
Implementa el método tiene_ciclo() que devuelva True si la lista tiene un ciclo y False si no. Sin modificar la lista y usando O(1) de memoria extra, es decir, sin guardar los nodos visitados en una lista o set.
La salida debe ser:
Lista normal (10 → 20 → 30 → None): tiene_ciclo() → False Lista con ciclo (40 apunta a 20): tiene_ciclo() → True Lista vacía: tiene_ciclo() → False Lista de un elemento sin ciclo: tiene_ciclo() → False Lista de un elemento con ciclo (apunta a sí mismo): tiene_ciclo() → True
💡 Pistas:
La solución clásica para detectar ciclos sin usar memoria extra es el algoritmo de Floyd, también llamado algoritmo de la liebre y la tortuga. Usa dos punteros que avanzan a distinta velocidad:
tortuga → avanza 1 nodo por iteración liebre → avanza 2 nodos por iteración Si no hay ciclo: liebre llegará a None antes que tortuga → False Si hay ciclo: liebre y tortuga se encontrarán en algún nodo → True
Lista con ciclo: [10] → [20] → [30] → [40] ──┐
↑ │
└────────────────────┘
Inicio: tortuga=[10], liebre=[10]
Paso 1: tortuga=[20], liebre=[30]
Paso 2: tortuga=[30], liebre=[20] ← liebre dio la vuelta por el ciclo
Paso 3: tortuga=[40], liebre=[40] ← ¡se encuentran! → hay ciclo
Los dos casos especiales críticos: lista vacía (__primero es None) y lista de un elemento. Si el único nodo apunta a sí mismo hay ciclo. Si apunta a None no lo hay. Compruébalos antes de entrar al bucle para evitar errores.
Para crear una lista con ciclo en las pruebas tendrás que acceder directamente a los nodos, la clase no expone ese nivel de detalle por diseño, así que en el ejercicio puedes crear los nodos manualmente:
# Crear lista con ciclo para probar
from linked_list import LinkedList
lista = LinkedList()
lista.insertar_detras(10)
lista.insertar_detras(20)
lista.insertar_detras(30)
lista.insertar_detras(40)
# Acceder al nodo interno para crear el ciclo (solo para la prueba)
nodo_actual = lista._LinkedList__primero
nodo_segundo = nodo_actual.siguiente
while nodo_actual.siguiente is not None:
nodo_actual = nodo_actual.siguiente
nodo_actual.siguiente = nodo_segundo # el último apunta al segundo → ciclo
Soluciones Comentadas
Solución Ejercicio 1:
def obtener(self, posicion):
"""Devuelve el valor en la posición dada (desde 0). Lanza IndexError si no existe."""
if posicion < 0 or posicion >= self.__longitud:
raise IndexError(
f"posición {posicion} fuera de rango (longitud {self.__longitud})"
)
actual = self.__primero
for _ in range(posicion):
actual = actual.siguiente
return actual.valor
def obtener_desde_final(self, posicion):
"""
Devuelve el valor en la posición desde el final (0=último).
Usa dos punteros — un solo recorrido, sin conocer la longitud.
"""
if posicion < 0:
raise IndexError(f"posición {posicion} no puede ser negativa")
# Adelantar el puntero rápido posicion+1 pasos
rapido = self.__primero
for _ in range(posicion + 1):
if rapido is None:
raise IndexError(
f"posición {posicion} desde el final fuera de rango"
)
rapido = rapido.siguiente
# Avanzar los dos juntos hasta que rápido llegue a None
lento = self.__primero
while rapido is not None:
lento = lento.siguiente
rapido = rapido.siguiente
# lento apunta al nodo en la posición correcta desde el final
return lento.valor
# ── Pruebas ────────────────────────────────────────────────────────────
lista = LinkedList()
for v in [10, 20, 30, 40, 50]:
lista.insertar_detras(v)
print(f"Lista: {lista}")
# → 10 → 20 → 30 → 40 → 50 → None
print(f"\nobtener(0) → {lista.obtener(0)}") # → 10
print(f"obtener(2) → {lista.obtener(2)}") # → 30
print(f"obtener(4) → {lista.obtener(4)}") # → 50
try:
lista.obtener(5)
except IndexError as e:
print(f"obtener(5) → IndexError: {e}")
# → IndexError: posición 5 fuera de rango (longitud 5)
try:
lista.obtener(-1)
except IndexError as e:
print(f"obtener(-1) → IndexError: {e}")
print(f"\nobtener_desde_final(0) → {lista.obtener_desde_final(0)}") # → 50
print(f"obtener_desde_final(1) → {lista.obtener_desde_final(1)}") # → 40
print(f"obtener_desde_final(4) → {lista.obtener_desde_final(4)}") # → 10
try:
lista.obtener_desde_final(5)
except IndexError as e:
print(f"obtener_desde_final(5) → IndexError: {e}")
Solución Ejercicio 2:
def eliminar_duplicados(self):
"""
Elimina duplicados en el lugar, manteniendo la primera aparición.
Modifica self — no crea lista nueva.
"""
if self.__primero is None: # lista vacía — nada que hacer
return
vistos = set()
vistos.add(self.__primero.valor)
anterior = self.__primero
actual = self.__primero.siguiente
while actual is not None:
if actual.valor in vistos:
# Es duplicado — eliminar: anterior no avanza
anterior.siguiente = actual.siguiente
actual = actual.siguiente
self.__longitud -= 1
else:
# Primera aparición — guardar y avanzar ambos
vistos.add(actual.valor)
anterior = actual
actual = actual.siguiente
# ── Pruebas ────────────────────────────────────────────────────────────
# Lista con duplicados
lista = LinkedList()
for v in [10, 20, 10, 30, 20, 40, 10]:
lista.insertar_detras(v)
print(f"Antes: {lista}")
lista.eliminar_duplicados()
print(f"Después: {lista}")
# → 10 → 20 → 30 → 40 → None
print(f"Longitud: {len(lista)}") # → 4
# Lista sin duplicados — no debe cambiar
lista2 = LinkedList()
for v in [5, 8, 3]:
lista2.insertar_detras(v)
print(f"\nAntes: {lista2}")
lista2.eliminar_duplicados()
print(f"Después: {lista2}")
# → 5 → 8 → 3 → None
# Lista con todos iguales
lista3 = LinkedList()
for v in [7, 7, 7, 7]:
lista3.insertar_detras(v)
print(f"\nAntes: {lista3}")
lista3.eliminar_duplicados()
print(f"Después: {lista3}")
# → 7 → None
print(f"Longitud: {len(lista3)}") # → 1
# Lista vacía — no debe lanzar error
lista4 = LinkedList()
lista4.eliminar_duplicados()
print(f"\nLista vacía después: {lista4}")
# → None
# Lista de un elemento — no debe cambiar
lista5 = LinkedList()
lista5.insertar_delante(42)
lista5.eliminar_duplicados()
print(f"Un elemento después: {lista5}")
# → 42 → None
Solución Ejercicio 3:
def tiene_ciclo(self):
"""
Detecta si la lista tiene un ciclo usando el algoritmo de Floyd.
O(n) tiempo, O(1) espacio — no usa memoria extra.
"""
# Caso especial — lista vacía o un solo nodo sin ciclo
if self.__primero is None:
return False
if self.__primero.siguiente is None:
return False
tortuga = self.__primero # avanza 1 nodo por iteración
liebre = self.__primero.siguiente # avanza 2 nodos por iteración
while liebre is not None and liebre.siguiente is not None:
if tortuga is liebre: # se encontraron → hay ciclo
return True
tortuga = tortuga.siguiente
liebre = liebre.siguiente.siguiente
return False # liebre llegó a None → no hay ciclo
# ── Pruebas ────────────────────────────────────────────────────────────
# Lista normal sin ciclo
lista_normal = LinkedList()
for v in [10, 20, 30, 40]:
lista_normal.insertar_detras(v)
print(f"Lista normal: {lista_normal}")
print(f"tiene_ciclo() → {lista_normal.tiene_ciclo()}") # → False
# Lista vacía
lista_vacia = LinkedList()
print(f"\nLista vacía:")
print(f"tiene_ciclo() → {lista_vacia.tiene_ciclo()}") # → False
# Lista de un elemento sin ciclo
lista_uno = LinkedList()
lista_uno.insertar_delante(42)
print(f"\nUn elemento sin ciclo:")
print(f"tiene_ciclo() → {lista_uno.tiene_ciclo()}") # → False
# Lista de un elemento con ciclo (apunta a sí mismo)
lista_ciclo_uno = LinkedList()
lista_ciclo_uno.insertar_delante(42)
nodo = lista_ciclo_uno._LinkedList__primero
nodo.siguiente = nodo # apunta a sí mismo
print(f"\nUn elemento con ciclo:")
print(f"tiene_ciclo() → {lista_ciclo_uno.tiene_ciclo()}") # → True
# Lista con ciclo (el último apunta al segundo)
lista_ciclo = LinkedList()
for v in [10, 20, 30, 40]:
lista_ciclo.insertar_detras(v)
# Crear el ciclo manualmente: [40] → [20]
nodo_actual = lista_ciclo._LinkedList__primero
nodo_segundo = nodo_actual.siguiente
while nodo_actual.siguiente is not None:
nodo_actual = nodo_actual.siguiente
nodo_actual.siguiente = nodo_segundo # [40] → [20]
print(f"\nLista con ciclo (40 → 20):")
print(f"tiene_ciclo() → {lista_ciclo.tiene_ciclo()}") # → True
Chuletario — LinkedList y estructuras encadenadas en Python
# ============================================
# CHULETARIO — LinkedList en Python
# Sergio Learns · sergiolearns.com
# ============================================
# ── NODO ─────────────────────────────────────────────────────
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor # el dato
self.siguiente = siguiente # referencia al siguiente o None
# Diagrama: [valor | siguiente ──►] → [valor | siguiente ──►] → None
# ── ESTRUCTURA LinkedList ────────────────────────────────────
class LinkedList:
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor
self.siguiente = siguiente
def __init__(self):
self.__primero = None # referencia al primer nodo
self.__longitud = 0 # número de elementos
# Lista vacía: primero → None
# Lista con datos: primero → [v1] → [v2] → [v3] → None
# ── OPERACIONES BÁSICAS ──────────────────────────────────────
# INSERTAR AL PRINCIPIO — O(1)
def insertar_delante(self, valor):
self.__primero = self.Nodo(valor, self.__primero)
self.__longitud += 1
# Diagrama:
# Antes: primero → [10] → [20] → None
# Después: primero → [5] → [10] → [20] → None
# INSERTAR AL FINAL — O(n)
def insertar_detras(self, valor):
nuevo = self.Nodo(valor)
if self.__primero is None: # caso especial: lista vacía
self.__primero = nuevo
else:
actual = self.__primero
while actual.siguiente is not None: # avanzar al último
actual = actual.siguiente
actual.siguiente = nuevo
self.__longitud += 1
# RECORRIDO — O(n) — el patrón más importante
actual = self.__primero
while actual is not None:
# hacer algo con actual.valor
actual = actual.siguiente # avanzar al siguiente
# ELIMINAR — O(n)
# Caso 1: eliminar el primero
self.__primero = self.__primero.siguiente
# Caso 2: eliminar cualquier otro (patrón anterior/actual)
anterior = self.__primero
actual = self.__primero.siguiente
while actual is not None:
if actual.valor == buscado:
anterior.siguiente = actual.siguiente # saltar el nodo
self.__longitud -= 1
break
anterior = actual # avanzar AMBOS cuando NO eliminas
actual = actual.siguiente
# BUSCAR — O(n)
actual = self.__primero
while actual is not None:
if actual.valor == buscado:
return True
actual = actual.siguiente
return False
# OBTENER POR POSICIÓN — O(n)
# Validar primero
if posicion < 0 or posicion >= self.__longitud:
raise IndexError(...)
actual = self.__primero
for _ in range(posicion):
actual = actual.siguiente
return actual.valor
# ── PATRONES AVANZADOS ───────────────────────────────────────
# PATRÓN 1 — acumulador en recorrido
# Para: contar, sumar, máximo, mínimo, filtrar
acumulador = valor_inicial
actual = primero
while actual is not None:
acumulador = operacion(acumulador, actual.valor)
actual = actual.siguiente
# PATRÓN 2 — tres variables para invertir punteros
# Para: invertir lista, operaciones que invierten referencias
anterior = None
actual = primero
while actual is not None:
siguiente = actual.siguiente # ← GUARDAR ANTES de modificar
actual.siguiente = anterior # ← invertir
anterior = actual # ← avanzar anterior
actual = siguiente # ← avanzar actual
primero = anterior # ← nuevo primero
# PATRÓN 3 — dos punteros a distinta velocidad
# Para: detectar ciclos (Floyd), encontrar elemento desde el final
tortuga = primero # avanza 1
liebre = primero # avanza 2
while liebre is not None and liebre.siguiente is not None:
if tortuga is liebre: # se encontraron → hay ciclo
return True
tortuga = tortuga.siguiente
liebre = liebre.siguiente.siguiente
return False
# PATRÓN 4 — inserción ordenada
# Para: mantener la lista ordenada al insertar
actual = primero
while actual.siguiente is not None and actual.siguiente.valor < nuevo_valor:
actual = actual.siguiente
nuevo.siguiente = actual.siguiente # conectar al resto
actual.siguiente = nuevo # conectar nuevo nodo
# PATRÓN 5 — anterior/actual para eliminar con condición
# Para: eliminar duplicados, eliminar todos los que cumplan algo
vistos = set()
anterior = primero
actual = primero.siguiente
while actual is not None:
if condicion(actual.valor):
anterior.siguiente = actual.siguiente # eliminar
actual = actual.siguiente
# anterior NO avanza cuando eliminas
else:
anterior = actual # avanzar AMBOS
actual = actual.siguiente # cuando NO eliminas
# ── MÉTODOS MÁGICOS ──────────────────────────────────────────
def __len__(self):
return self.__longitud
def __str__(self):
return ' → '.join(str(v) for v in self) + ' → None'
def __repr__(self):
return f'LinkedList({list(self)})'
def __iter__(self): # hace la lista iterable con for
actual = self.__primero
while actual is not None:
valor = actual.valor
actual = actual.siguiente # avanzar ANTES del yield
yield valor # pausa aquí
def __contains__(self, valor):
return self.contiene(valor)
# ── LinkedList vs LISTA DE PYTHON ────────────────────────────
# Lista Python LinkedList
# ─────────────────────────────────────────────────
# Acceso por índice: O(1) ✓ O(n) ✗
# Insertar al principio: O(n) ✗ O(1) ✓
# Insertar al final: O(1) ✓ O(n) ✗
# Insertar en el medio: O(n) ✗ O(1) ✓ (con nodo anterior)
# Buscar: O(n) O(n)
# Memoria: más eficiente menos eficiente
# ── ERRORES TÍPICOS ──────────────────────────────────────────
# ERROR 1 — modificar el puntero antes de guardar el siguiente
# PIERDE el resto de la lista
# MAL
actual.siguiente = anterior # ← ya no puedes llegar al siguiente
siguiente = actual.siguiente # ← esto ahora da anterior, no el real
# BIEN
siguiente = actual.siguiente # ← guardar PRIMERO
actual.siguiente = anterior # ← luego modificar
# ERROR 2 — olvidar el caso especial de lista vacía
# Siempre comprobar self.__primero is None antes de acceder a .valor o .siguiente
def metodo(self):
if self.__primero is None: # ← comprobar siempre
return None # o raise o lo que corresponda
# ... resto del método
# ERROR 3 — olvidar el caso especial de eliminar el primero
# El patrón anterior/actual empieza en el segundo nodo
# Si el elemento a eliminar ES el primero necesitas manejarlo aparte
if self.__primero.valor == buscado:
self.__primero = self.__primero.siguiente # caso especial
return
# ... el resto del código con anterior/actual
# ERROR 4 — avanzar anterior cuando eliminas un nodo
# Al eliminar, anterior NO avanza — sigue apuntando al mismo nodo
if duplicado:
anterior.siguiente = actual.siguiente # eliminar
actual = actual.siguiente # avanzar solo actual
# NO hacer: anterior = actual
else:
anterior = actual # avanzar ambos
actual = actual.siguiente # solo cuando NO eliminas
# ERROR 5 — recorrer una lista con ciclo sin detectarlo
# Un while actual is not None en una lista con ciclo → bucle infinito
# Detectar ciclo primero con el algoritmo de Floyd si no estás seguro
Python LinkedList — exercises to master linked structures
These exercises close out this block and with it the complete FP2 syllabus. Theory and practice done. Now solve on your own. Three exercises, three levels. The thread running through all three: the two mistakes that destroy most LinkedList implementations are modifying a pointer before saving the next one, and forgetting the special cases of empty list or single element.
As always: try to solve it yourself, use the hint if stuck for more than 10 minutes, compare with the commented solution at the end.
Basic Level
Exercise 1 — Get element at position N
Add get(position) method returning the value at the given position (from 0). Raise IndexError if position doesn’t exist.
lst: 10 → 20 → 30 → 40 → 50 → None lst.get(0) → 10 lst.get(2) → 30 lst.get(4) → 50 lst.get(5) → IndexError lst.get(-1) → IndexError
Bonus challenge: get_from_end(position) returning element counting from the end (0=last, 1=second-to-last). Without knowing the length and in a single traversal.
lst.get_from_end(0) → 50 lst.get_from_end(1) → 40 lst.get_from_end(4) → 10
💡 Hint — forgetting special cases:
# WRONG — doesn't validate position
def get(self, position):
current = self.__first
for i in range(position):
current = current.next_node # AttributeError if position > length
return current.value # AttributeError if empty list
# RIGHT — validate first
def get(self, position):
if position < 0 or position >= self.__length:
raise IndexError(f"position {position} out of range (length {self.__length})")
current = self.__first
for _ in range(position):
current = current.next_node
return current.value
For get_from_end without knowing the length, use two pointers at different speeds — one stays N steps ahead of the other:
Want element at position 1 from end (second-to-last) in list: 10 → 20 → 30 → 40 → 50 → None Advance fast pointer N+1 steps (2 steps): fast → [30], slow → [10] Advance both until fast reaches None: fast=[30], slow=[10] → fast=[40], slow=[20] fast=[40], slow=[20] → fast=[50], slow=[30] fast=[50], slow=[30] → fast=None, slow=[40] fast=None → slow points to second-to-last → return 40 ✓
Intermediate Level
Exercise 2 — Remove duplicates from a LinkedList
Add remove_duplicates() that removes all duplicate occurrences keeping only the first appearance of each value. Modifies the list in place.
Before: 10 → 20 → 10 → 30 → 20 → 40 → 10 → None After: 10 → 20 → 30 → 40 → None All same: Before: 7 → 7 → 7 → 7 → None After: 7 → None
💡 Hints:
The modify-before-saving mistake appears subtly here. The key is knowing when to advance previous:
if value in seen:
previous.next_node = current.next_node # remove node
current = current.next_node
# previous does NOT advance when you delete
else:
seen.add(current.value)
previous = current # advance BOTH
current = current.next_node # only when NOT deleting
Empty list and single element special cases: the method must work without doing anything or raising errors.
Use a set to track seen values — O(1) membership check:
seen = set() # if current.value in seen → duplicate → remove # if current.value not in seen → first occurrence → add to seen
Final Challenge
Exercise 3 — Detect if a LinkedList has a cycle
A LinkedList has a cycle when one of its nodes points to a previous node instead of advancing toward None — making traversal infinite.
Normal: [10] → [20] → [30] → [40] → None
With cycle (last points to second):
[10] → [20] → [30] → [40]
↑ |
└───────────────┘
Implement has_cycle() returning True if cycle exists, False otherwise. Without modifying the list and using O(1) extra memory — no list or set of visited nodes.
💡 Hints:
The classic solution is Floyd’s algorithm — the tortoise and hare:
tortoise → advances 1 node per iteration hare → advances 2 nodes per iteration No cycle: hare reaches None first → False Cycle: hare and tortoise meet at some node → True
Cycle: [10] → [20] → [30] → [40] ──┐
↑ │
└────────────────────┘
Start: tortoise=[10], hare=[10]
Step 1: tortoise=[20], hare=[30]
Step 2: tortoise=[30], hare=[20] ← hare looped back
Step 3: tortoise=[40], hare=[40] ← they meet! → cycle
Two critical special cases: empty list and single element. Check them before entering the loop.
(Solutions same as Spanish version)
Cheat sheet — Python LinkedList
# ============================================
# CHEAT SHEET — Python LinkedList
# Sergio Learns · sergiolearns.com
# ============================================
# NODE
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next_node = next_node
# Diagram: [value | next ──►] → [value | next ──►] → None
# LINKED LIST
class LinkedList:
def __init__(self):
self.__first = None
self.__length = 0
# INSERT AT FRONT — O(1)
self.__first = self.Node(value, self.__first)
# INSERT AT BACK — O(n)
if self.__first is None: self.__first = new # empty list
else:
current = self.__first
while current.next_node is not None: current = current.next_node
current.next_node = new
# TRAVERSAL — O(n) — the most important pattern
current = self.__first
while current is not None:
# do something with current.value
current = current.next_node
# DELETE — O(n)
# Special case: delete first
self.__first = self.__first.next_node
# General case: previous/current pair
previous = self.__first
current = self.__first.next_node
while current is not None:
if current.value == target:
previous.next_node = current.next_node
break
previous = current
current = current.next_node
# PATTERN 1 — accumulator traversal (count, sum, max, filter)
accumulator = initial_value
current = first
while current is not None:
accumulator = operation(accumulator, current.value)
current = current.next_node
# PATTERN 2 — three variables to reverse pointers
previous = None
current = first
while current is not None:
next_node = current.next_node # SAVE BEFORE modifying
current.next_node = previous # reverse
previous = current # advance
current = next_node # advance
first = previous
# PATTERN 3 — two pointers at different speeds (Floyd)
tortoise = first
hare = first
while hare is not None and hare.next_node is not None:
if tortoise is hare: return True # cycle detected
tortoise = tortoise.next_node
hare = hare.next_node.next_node
return False
# PATTERN 4 — sorted insertion
current = first
while current.next_node is not None and current.next_node.value < new_value:
current = current.next_node
new.next_node = current.next_node
current.next_node = new
# PATTERN 5 — previous/current to delete with condition
seen = set()
previous = first
current = first.next_node
while current is not None:
if condition(current.value):
previous.next_node = current.next_node # remove
current = current.next_node # advance only current
else:
previous = current # advance BOTH
current = current.next_node # only when NOT removing
# COMMON MISTAKES
# 1. Modify pointer before saving next → lose the list
next_node = current.next_node # SAVE FIRST
current.next_node = previous # THEN modify
# 2. Forget empty list special case → AttributeError
if self.__first is None: return # always check first
# 3. Forget first-node special case in delete
if self.__first.value == target:
self.__first = self.__first.next_node
return
# then previous/current for the rest
# 4. Advance previous when deleting
# When deleting: previous stays, only current advances
# When keeping: both advance
# 5. Traversing a list with cycle → infinite loop
# Always detect cycle first with Floyd if unsure
# LinkedList vs Python list
# Python list: O(1) index, O(1) append, O(n) insert middle
# LinkedList: O(n) index, O(n) append, O(1) insert at front
