Invertir una Lista Enlazada

El problema

Dado el nodo cabeza de una lista enlazada, invertir la lista y retornar la nueva cabeza.

Entrada:  1 -> 2 -> 3 -> 4 -> 5 -> NULL
Salida:   5 -> 4 -> 3 -> 2 -> 1 -> NULL

Este es uno de los problemas más clásicos en entrevistas y competencias.

Estructura del nodo

struct Nodo {
    int dato;
    Nodo* siguiente;
    Nodo(int x) : dato(x), siguiente(nullptr) {}
};

Método 1: Iterativo

La idea es recorrer la lista y cambiar la dirección de cada puntero:

Original: 1 -> 2 -> 3 -> NULL

Paso 1: NULL <- 1    2 -> 3 -> NULL
Paso 2: NULL <- 1 <- 2    3 -> NULL
Paso 3: NULL <- 1 <- 2 <- 3

Final: 3 -> 2 -> 1 -> NULL

Implementación

Nodo* invertirIterativo(Nodo* cabeza) {
    Nodo* anterior = nullptr;
    Nodo* actual = cabeza;

    while (actual != nullptr) {
        Nodo* siguiente = actual->siguiente;  // Guardar siguiente
        actual->siguiente = anterior;         // Invertir enlace
        anterior = actual;                    // Mover anterior
        actual = siguiente;                   // Mover actual
    }

    return anterior;  // Nueva cabeza
}

Visualización paso a paso

// Lista: 1 -> 2 -> 3 -> NULL
//
// Inicio:
// anterior = NULL
// actual = 1
//
// Iteración 1:
// siguiente = 2
// 1->siguiente = NULL  (1 -> NULL)
// anterior = 1
// actual = 2
// Estado: NULL <- 1    2 -> 3 -> NULL
//
// Iteración 2:
// siguiente = 3
// 2->siguiente = 1     (2 -> 1)
// anterior = 2
// actual = 3
// Estado: NULL <- 1 <- 2    3 -> NULL
//
// Iteración 3:
// siguiente = NULL
// 3->siguiente = 2     (3 -> 2)
// anterior = 3
// actual = NULL
// Estado: NULL <- 1 <- 2 <- 3
//
// Fin: retornar 3 (nueva cabeza)

Complejidad:

• Tiempo: $O(n)$
• Espacio: $O(1)$

Método 2: Recursivo

La recursión procesa del final hacia el inicio:

Nodo* invertirRecursivo(Nodo* cabeza) {
    // Caso base: lista vacía o un solo nodo
    if (cabeza == nullptr || cabeza->siguiente == nullptr) {
        return cabeza;
    }

    // Invertir el resto de la lista
    Nodo* nuevaCabeza = invertirRecursivo(cabeza->siguiente);

    // Invertir el enlace actual
    cabeza->siguiente->siguiente = cabeza;
    cabeza->siguiente = nullptr;

    return nuevaCabeza;
}

Visualización recursiva

invertir(1 -> 2 -> 3 -> NULL)
│
├─ invertir(2 -> 3 -> NULL)
│  │
│  ├─ invertir(3 -> NULL)
│  │  └─ retorna 3 (caso base)
│  │
│  │  // 2->siguiente->siguiente = 2  =>  3->siguiente = 2
│  │  // 2->siguiente = NULL
│  │  // Estado: 3 -> 2 -> NULL
│  └─ retorna 3
│
│  // 1->siguiente->siguiente = 1  =>  2->siguiente = 1
│  // 1->siguiente = NULL
│  // Estado: 3 -> 2 -> 1 -> NULL
└─ retorna 3

Complejidad:

• Tiempo: $O(n)$
• Espacio: $O(n)$ (pila de recursión)

Método 3: Usando stack

Nodo* invertirConStack(Nodo* cabeza) {
    if (cabeza == nullptr) return nullptr;

    stack<Nodo*> pila;
    Nodo* actual = cabeza;

    // Agregar todos los nodos al stack
    while (actual != nullptr) {
        pila.push(actual);
        actual = actual->siguiente;
    }

    // La nueva cabeza es el tope del stack
    Nodo* nuevaCabeza = pila.top();
    pila.pop();

    actual = nuevaCabeza;
    while (!pila.empty()) {
        actual->siguiente = pila.top();
        pila.pop();
        actual = actual->siguiente;
    }
    actual->siguiente = nullptr;

    return nuevaCabeza;
}

Complejidad:

• Tiempo: $O(n)$
• Espacio: $O(n)$

Variantes del problema

Invertir en grupos de k

Invertir la lista en grupos de tamaño k.

Entrada: 1 -> 2 -> 3 -> 4 -> 5, k = 2
Salida:  2 -> 1 -> 4 -> 3 -> 5

Nodo* invertirEnGrupos(Nodo* cabeza, int k) {
    Nodo* actual = cabeza;
    Nodo* anterior = nullptr;
    Nodo* siguiente = nullptr;

    // Verificar si hay al menos k nodos
    Nodo* check = cabeza;
    for (int i = 0; i < k; i++) {
        if (check == nullptr) return cabeza;
        check = check->siguiente;
    }

    // Invertir k nodos
    int count = 0;
    while (actual != nullptr && count < k) {
        siguiente = actual->siguiente;
        actual->siguiente = anterior;
        anterior = actual;
        actual = siguiente;
        count++;
    }

    // Recursivamente invertir el resto
    if (siguiente != nullptr) {
        cabeza->siguiente = invertirEnGrupos(siguiente, k);
    }

    return anterior;  // Nueva cabeza del grupo
}

Invertir entre posiciones m y n

Entrada: 1 -> 2 -> 3 -> 4 -> 5, m = 2, n = 4
Salida:  1 -> 4 -> 3 -> 2 -> 5

Nodo* invertirEntre(Nodo* cabeza, int m, int n) {
    if (cabeza == nullptr || m == n) return cabeza;

    Nodo dummy(0);
    dummy.siguiente = cabeza;
    Nodo* pre = &dummy;

    // Mover pre al nodo antes de posición m
    for (int i = 1; i < m; i++) {
        pre = pre->siguiente;
    }

    Nodo* inicio = pre->siguiente;
    Nodo* siguiente = inicio->siguiente;

    // Invertir n - m veces
    for (int i = 0; i < n - m; i++) {
        inicio->siguiente = siguiente->siguiente;
        siguiente->siguiente = pre->siguiente;
        pre->siguiente = siguiente;
        siguiente = inicio->siguiente;
    }

    return dummy.siguiente;
}

Verificar si es palíndromo

Usa inversión para verificar si la lista es un palíndromo.

bool esPalindromo(Nodo* cabeza) {
    if (cabeza == nullptr || cabeza->siguiente == nullptr) {
        return true;
    }

    // Encontrar el medio
    Nodo* lento = cabeza;
    Nodo* rapido = cabeza;
    while (rapido->siguiente != nullptr && rapido->siguiente->siguiente != nullptr) {
        lento = lento->siguiente;
        rapido = rapido->siguiente->siguiente;
    }

    // Invertir la segunda mitad
    Nodo* segundaMitad = invertirIterativo(lento->siguiente);

    // Comparar
    Nodo* p1 = cabeza;
    Nodo* p2 = segundaMitad;
    bool resultado = true;

    while (p2 != nullptr) {
        if (p1->dato != p2->dato) {
            resultado = false;
            break;
        }
        p1 = p1->siguiente;
        p2 = p2->siguiente;
    }

    // Restaurar la lista (opcional)
    lento->siguiente = invertirIterativo(segundaMitad);

    return resultado;
}

Código completo para practicar

#include <bits/stdc++.h>
using namespace std;

struct Nodo {
    int dato;
    Nodo* siguiente;
    Nodo(int x) : dato(x), siguiente(nullptr) {}
};

// Crear lista desde vector
Nodo* crearLista(vector<int>& valores) {
    if (valores.empty()) return nullptr;

    Nodo* cabeza = new Nodo(valores[0]);
    Nodo* actual = cabeza;

    for (int i = 1; i < valores.size(); i++) {
        actual->siguiente = new Nodo(valores[i]);
        actual = actual->siguiente;
    }

    return cabeza;
}

// Imprimir lista
void imprimir(Nodo* cabeza) {
    while (cabeza != nullptr) {
        cout << cabeza->dato;
        if (cabeza->siguiente) cout << " -> ";
        cabeza = cabeza->siguiente;
    }
    cout << " -> NULL" << endl;
}

// Invertir iterativo
Nodo* invertir(Nodo* cabeza) {
    Nodo* anterior = nullptr;
    Nodo* actual = cabeza;

    while (actual != nullptr) {
        Nodo* siguiente = actual->siguiente;
        actual->siguiente = anterior;
        anterior = actual;
        actual = siguiente;
    }

    return anterior;
}

// Liberar memoria
void liberar(Nodo* cabeza) {
    while (cabeza != nullptr) {
        Nodo* temp = cabeza;
        cabeza = cabeza->siguiente;
        delete temp;
    }
}

int main() {
    vector<int> valores = {1, 2, 3, 4, 5};
    Nodo* lista = crearLista(valores);

    cout << "Original: ";
    imprimir(lista);

    lista = invertir(lista);

    cout << "Invertida: ";
    imprimir(lista);

    liberar(lista);
    return 0;
}

Errores comunes

1. Perder la referencia al siguiente

// ❌ MAL
while (actual != nullptr) {
    actual->siguiente = anterior;  // ¡Perdimos el siguiente!
    anterior = actual;
    actual = actual->siguiente;    // Siempre será anterior
}

// ✅ BIEN
while (actual != nullptr) {
    Nodo* siguiente = actual->siguiente;  // Guardar primero
    actual->siguiente = anterior;
    anterior = actual;
    actual = siguiente;
}

2. No manejar casos especiales

// ✅ Siempre verificar
if (cabeza == nullptr || cabeza->siguiente == nullptr) {
    return cabeza;
}

3. No actualizar el puntero de retorno

// ❌ MAL
Nodo* invertir(Nodo* cabeza) {
    // ... invertir ...
    return cabeza;  // ¡Sigue apuntando al viejo inicio!
}

// ✅ BIEN
Nodo* invertir(Nodo* cabeza) {
    // ... invertir ...
    return anterior;  // Retornar la nueva cabeza
}

Resumen

Ejercicios recomendados

1. LeetCode - Reverse Linked List
2. LeetCode - Reverse Linked List II
3. LeetCode - Reverse Nodes in k-Group
4. LeetCode - Palindrome Linked List
5. LeetCode - Swap Nodes in Pairs