0Pricing
Coding Interview Prep · Lección

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.next

Trazado 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)  # 3

Inversió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.next

Invertir 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.next

Invertir 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.next

Lista 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])))    # False

Comparació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.next

Reordenar 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.next

Resumen: 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.

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

  1. Clase Node y construcción de listas
  2. Inversión de una lista enlazada
  3. Detección de ciclos con el algoritmo de Floyd
  4. Combinar, dividir y encontrar el enésimo elemento desde el final
← Volver a Coding Interview Prep