Invertir una Lista Enlazada

El problema

Dada una lista enlazada 1 → 2 → 3 → 4 → nullptr, transformarla en 4 → 3 → 2 → 1 → nullptr.

Es como voltear una fila de fichas de dominó: cada ficha que apuntaba a la derecha ahora apunta a la izquierda.

Solución iterativa (tres punteros)

La idea es recorrer la lista y, nodo por nodo, invertir la dirección del puntero siguiente.

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

    while (actual != nullptr) {
        Nodo* siguiente = actual->siguiente; // Guardar referencia al siguiente
        actual->siguiente = anterior;        // Invertir el puntero
        anterior = actual;                   // Avanzar anterior
        actual = siguiente;                  // Avanzar actual
    }

    return anterior;  // anterior ahora es la nueva cabeza
}

Paso a paso visual

Lista original: 1 → 2 → 3 → nullptr

Resultado: 3 → 2 → 1 → nullptr ✅

Solución recursiva

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

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

    // El siguiente nodo debe apuntar a mí
    nodo->siguiente->siguiente = nodo;
    nodo->siguiente = nullptr;

    return nuevaCabeza;
}

¿Cómo funciona? La recursión llega hasta el último nodo (que será la nueva cabeza). Al regresar, cada nodo le dice a su siguiente: "ahora apunta a mí" y se desconecta del que sigue.

Variantes comunes

Invertir solo una porción (de posición L a R)

Nodo* invertirEntre(Nodo* cabeza, int L, int R) {
    if (L == R) return cabeza;

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

    for (int i = 1; i < L; i++) {
        preL = preL->siguiente;
    }

    Nodo* actual = preL->siguiente;
    for (int i = 0; i < R - L; i++) {
        Nodo* temp = actual->siguiente;
        actual->siguiente = temp->siguiente;
        temp->siguiente = preL->siguiente;
        preL->siguiente = temp;
    }

    return dummy.siguiente;
}

Invertir en grupos de K

Invertir cada grupo de K nodos:

1 → 2 → 3 → 4 → 5 → 6 con K=3 → 3 → 2 → 1 → 6 → 5 → 4

Nodo* invertirEnGrupos(Nodo* cabeza, int k) {
    Nodo* actual = cabeza;
    int count = 0;

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

    // Invertir k nodos
    Nodo* anterior = nullptr;
    actual = cabeza;
    while (actual != nullptr && count < k) {
        Nodo* sig = actual->siguiente;
        actual->siguiente = anterior;
        anterior = actual;
        actual = sig;
        count++;
    }

    // Recursión para el resto
    cabeza->siguiente = invertirEnGrupos(actual, k);

    return anterior;
}

Detectar ciclo (Floyd)

Otro problema clásico: ¿tiene la lista un ciclo?

bool tieneCiclo(Nodo* cabeza) {
    Nodo* lento = cabeza;
    Nodo* rapido = cabeza;

    while (rapido != nullptr && rapido->siguiente != nullptr) {
        lento = lento->siguiente;          // Avanza 1 paso
        rapido = rapido->siguiente->siguiente;  // Avanza 2 pasos

        if (lento == rapido) return true;   // Se encontraron: hay ciclo
    }

    return false;  // Rápido llegó al final: no hay ciclo
}

Analogía: Dos corredores en una pista circular. El rápido (2x velocidad) eventualmente alcanza al lento si la pista es circular. Si la pista tiene fin, el rápido llega primero al final.

Encontrar el medio de la lista

Nodo* encontrarMedio(Nodo* cabeza) {
    Nodo* lento = cabeza;
    Nodo* rapido = cabeza;

    while (rapido != nullptr && rapido->siguiente != nullptr) {
        lento = lento->siguiente;
        rapido = rapido->siguiente->siguiente;
    }

    return lento;  // Lento está en el medio
}

Cuando el rápido llega al final (avanzando 2 pasos), el lento está exactamente a la mitad.

Programa completo de ejemplo

#include <iostream>
using namespace std;

struct Nodo {
    int dato;
    Nodo* sig;
    Nodo(int d) : dato(d), sig(nullptr) {}
};

void imprimir(Nodo* cabeza) {
    Nodo* act = cabeza;
    while (act) {
        cout << act->dato;
        if (act->sig) cout << " -> ";
        act = act->sig;
    }
    cout << " -> nullptr" << endl;
}

Nodo* invertir(Nodo* cabeza) {
    Nodo* ant = nullptr;
    Nodo* act = cabeza;
    while (act) {
        Nodo* sig = act->sig;
        act->sig = ant;
        ant = act;
        act = sig;
    }
    return ant;
}

int main() {
    // Crear lista: 1 -> 2 -> 3 -> 4 -> 5
    Nodo* cabeza = new Nodo(1);
    Nodo* act = cabeza;
    for (int i = 2; i <= 5; i++) {
        act->sig = new Nodo(i);
        act = act->sig;
    }

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

    cabeza = invertir(cabeza);

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

    return 0;
}

Salida:

Original: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
Invertida: 5 -> 4 -> 3 -> 2 -> 1 -> nullptr

Ejercicio de práctica

Determina si una lista enlazada es un palíndromo (se lee igual al derecho y al revés). Ejemplo: 1 → 2 → 3 → 2 → 1 es palíndromo.

bool esPalindromo(Nodo* cabeza) {
    if (!cabeza || !cabeza->sig) return true;

    // 1. Encontrar el medio
    Nodo* lento = cabeza;
    Nodo* rapido = cabeza;
    while (rapido->sig && rapido->sig->sig) {
        lento = lento->sig;
        rapido = rapido->sig->sig;
    }

    // 2. Invertir la segunda mitad
    Nodo* segundaMitad = invertir(lento->sig);

    // 3. Comparar ambas mitades
    Nodo* p1 = cabeza;
    Nodo* p2 = segundaMitad;
    bool resultado = true;
    while (p2) {
        if (p1->dato != p2->dato) {
            resultado = false;
            break;
        }
        p1 = p1->sig;
        p2 = p2->sig;
    }

    // 4. Restaurar la lista (opcional)
    lento->sig = invertir(segundaMitad);

    return resultado;
}