Listas enlazadas
Invertir una lista enlazada simple
Dada la cabeza de una lista enlazada simple, invertir el orden de sus nodos in-place y devolver la nueva cabeza. Restricciones: O(n) tiempo, O(1) espacio.
- 1 Tres punteros
Mantener prev = nullptr y recorrer con head. En cada paso guardamos next = head->next antes de reescribir el enlace, para no perder el resto de la lista.
- 2 Reconectar y avanzar
En cada nodo: head->next = prev; prev = head; head = next. Al terminar, prev apunta a la antigua cola, que ahora es la nueva cabeza.
- 3 Complejidad
Cada nodo se visita exactamente una vez → O(n) en tiempo; solo se usan tres punteros auxiliares → O(1) en espacio.
C++
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* next = head->next; // guardar el resto
head->next = prev; // invertir el enlace
prev = head; // avanzar prev
head = next; // avanzar head
}
return prev; // nueva cabeza
}
Solución
prev queda como la nueva cabeza de la lista invertida. El algoritmo es un único recorrido lineal sin memoria adicional proporcional a n.