Inversión de una lista enlazada
Invierta una lista enlazada simple de forma iterativa, reajustando tres punteros, y de forma recursiva, siguiendo cada paso en un diagrama tipo pizarra.
Inversión de una lista enlazada es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Por qué es esencial invertir listas
Invertir una lista enlazada es una de las preguntas más frecuentes en las entrevistas de programación. Pone a prueba su capacidad para manipular punteros con precisión sin perder de vista los nodos. Sus variantes aparecen como problemas independientes y como pasos dentro de algoritmos más grandes, como la detección de palíndromos, la reorganización de listas y la inversión por grupos de k elementos.
El enfoque iterativo utiliza tres punteros: prev, curr y next_node. El enfoque recursivo expresa la misma lógica mediante un recorrido de la pila de llamadas. Ambos logran un tiempo O(n) y, en el caso del enfoque iterativo, un espacio O(1).
Inversión iterativa con tres punteros
En cada paso de la inversión iterativa: guarde curr.next para no perder el resto de la lista, haga que curr.next apunte hacia atrás a prev, avance prev hasta curr y avance curr hasta el siguiente nodo guardado. Cuando curr se convierta en None, el bucle termina y prev es la nueva cabecera.
Una regla mnemotécnica útil: Guardar, invertir, avanzar, avanzar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save
curr.next = prev # Flip
prev = curr # Advance prev
curr = next_node # Advance curr
return prev # new head
# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
print(head.val, end=' ') # 5 4 3 2 1
head = head.nextTrazado paso a paso
Sigamos el trazado de reverse_list sobre 1 -> 2 -> 3. Inicialmente, prev=None, curr=1. Paso 1: guarde next=2, invierta 1.next=None, prev=1, curr=2. Paso 2: guarde next=3, invierta 2.next=1, prev=2, curr=3. Paso 3: guarde next=None, invierta 3.next=2, prev=3, curr=None. El bucle termina; devuelva prev=3, que es la nueva cabeza de 3 -> 2 -> 1.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_traced(head):
prev, curr = None, head
step = 0
while curr:
step += 1
next_node = curr.next
curr.next = prev
print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
prev = curr
curr = next_node
return prev
nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val) # 3Inversión recursiva
El enfoque recursivo confía en que reverse_list(head.next) devuelve la nueva cabeza del sufijo ya invertido. Solo queda invertir el puntero entre head y head.next: establezca head.next.next = head (haga que el antiguo segundo nodo apunte al antiguo primero) y head.next = None (corte el antiguo enlace hacia delante). La nueva cabeza asciende desde el caso base.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_rec(head):
# Base case: empty or single node
if not head or not head.next:
return head
new_head = reverse_list_rec(head.next) # reverse suffix
head.next.next = head # former second node points back
head.next = None # sever forward link
return new_head
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
print(head.val, end=' ') # 4 3 2 1
head = head.nextInvertir una sublista (LeetCode 92)
LeetCode 92 'Reverse Linked List II' le solicita invertir la sublista desde la posición left hasta la right (con índices que comienzan en 1) en una sola pasada. El truco consiste en localizar el nodo anterior a la sublista (use una cabeza ficticia para que esto siempre sea válido), realizar después la inversión de tres punteros durante exactamente (right - left) pasos y, por último, volver a conectar el segmento invertido con el resto de la lista.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(head, left, right):
dummy = ListNode(0, head)
pre = dummy
# Advance pre to node just before position 'left'
for _ in range(left - 1):
pre = pre.next
curr = pre.next
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = pre.next
pre.next = next_node
return dummy.next
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
print(head.val, end=' ') # 1 4 3 2 5
head = head.nextInvertir nodos en grupos de k (LeetCode 25)
LeetCode 25 'Reverse Nodes in k-Group' invierte cada grupo consecutivo de k nodos. El enfoque es el siguiente: compruebe si quedan k nodos; si no, déjelos sin cambios. Invierta los siguientes k nodos usando el método iterativo, después invierta recursivamente el resto de la lista y conéctelo. La complejidad temporal sigue siendo O(n), con una profundidad de llamadas recursivas de O(n/k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseKGroup(head, k):
# Check if k nodes are available
curr, count = head, 0
while curr and count < k:
curr = curr.next
count += 1
if count < k:
return head # fewer than k nodes left, keep as-is
# Reverse k nodes
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head is now the tail of the reversed group
head.next = reverseKGroup(curr, k)
return prev
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
print(head.val, end=' ') # 2 1 4 3 5
head = head.nextLista enlazada palíndroma
LeetCode 234 'Palindrome Linked List': compruebe si una lista enlazada es un palíndromo en tiempo O(n) y espacio O(1). La estrategia consiste en encontrar el punto medio con punteros lento y rápido, invertir la segunda mitad in situ, comparar ambas mitades nodo a nodo y, opcionalmente, restaurar la lista. Esto combina la búsqueda del punto medio y la inversión, dos habilidades fundamentales.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head):
# Find mid
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
def build(arr):
d = ListNode(0)
c = d
for v in arr:
c.next = ListNode(v)
c = c.next
return d.next
print(isPalindrome(build([1,2,2,1]))) # True
print(isPalindrome(build([1,2,3]))) # FalseComparación entre iterativo y recursivo
La inversión iterativa utiliza espacio O(1) y, por lo general, es la opción preferida. La inversión recursiva utiliza espacio O(n) en la pila debido a la profundidad de las llamadas, lo que puede provocar un desbordamiento de pila en listas muy largas (el límite predeterminado de Python es de aproximadamente 1000 niveles de recursión).
En una entrevista, implemente primero la versión iterativa para demostrar que tiene en cuenta las restricciones de espacio y, después, mencione la versión recursiva como una alternativa más limpia si la longitud de la lista está acotada.
import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint
# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)Errores comunes al invertir
Tres errores explican casi todos los fallos al invertir una lista. Primero, no guardar next antes de sobrescribirlo: curr.next = prev destruye la referencia hacia delante si no se había guardado next_node. Segundo, no devolver prev: al final del bucle, curr es None, pero prev es la nueva cabeza. Tercero, usar un caso base recursivo incorrecto: olvidar not head.next impide gestionar una lista de un solo nodo y provoca un AttributeError.
# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # BUG if omitted: lose rest of list
curr.next = prev
prev = curr
curr = next_node
return prev # BUG if you return curr: it is None
nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
print(h.val, end=' ') # 3 2 1
h = h.nextReordenar la lista (LeetCode 143)
LeetCode 143 'Reorder List' reorganiza L0 → L1 → L2 → ... → Ln como L0 → Ln → L1 → Ln-1 → L2 → Ln-2 en tiempo O(n) y espacio O(1). La solución combina tres pasos: encontrar el punto medio, invertir la segunda mitad e intercalar ambas mitades. Dominar la inversión convierte este problema aparentemente complejo en una combinación directa de herramientas conocidas.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
if not head or not head.next:
return
# Find mid
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Interleave
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
print(h.val, end=' ') # 1 4 2 3
h = h.nextResumen: la inversión es un bloque de construcción
Invertir una lista enlazada rara vez es el objetivo final: es un bloque de construcción. La detección de palíndromos, la inversión en grupos de k, la reordenación de listas y la inversión entre posiciones dependen del mismo patrón iterativo de tres punteros. Una vez que el patrón sea automático, podrá concentrar su atención en la estructura del problema de nivel superior.
Practique siempre la inversión hasta que pueda escribirla de memoria en menos de dos minutos; aparecerá de alguna forma en casi todas las entrevistas sobre listas enlazadas.
Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: el patrón iterativo Guardar-Invertir-Avanzar-Avanzar invierte una lista en tiempo O(n) y espacio O(1), el enfoque recursivo confía en que el sufijo ya está invertido y solo corrige el último enlace, y la inversión es un subpaso fundamental en la detección de palíndromos, la reordenación de listas y la inversión en grupos de k. A continuación exploraremos la detección de ciclos con el algoritmo de Floyd.
Aprende Coding Interview Prep con un tutor de IA — gratis
Escribe y ejecuta código real en tu navegador, obtén ayuda instantánea de un tutor de IA disponible 24/7 y continúa donde lo dejaste en la web o en la aplicación.
- Cursos
- 90
- Lecciones
- 360
Preguntas frecuentes
¿La lección «Inversión de una lista enlazada» es gratis?
Sí — el texto completo de «Inversión de una lista enlazada» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Inversión de una lista enlazada»?
Invierta una lista enlazada simple de forma iterativa, reajustando tres punteros, y de forma recursiva, siguiendo cada paso en un diagrama tipo pizarra. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Inversión de una lista enlazada»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Clase Node y construcción de listas
- Inversión de una lista enlazada
- Detección de ciclos con el algoritmo de Floyd
- Combinar, dividir y encontrar el enésimo elemento desde el final