Invertir una lista enlazada

  
Introducción
       
En este artículo, aprenderás a invertir una lista enlazada. Este es un problema de programación común que se puede encontrar en entrevistas de trabajo, como las de Facebook.

En este artículo, cubriremos los siguientes temas:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript

Una solución simple a este problema consiste en utilizar un puntero auxiliar para recorrer la lista enlazada en orden inverso. A medida que el puntero auxiliar se mueve, se actualizan los enlaces de los nodos para que apunten al nodo anterior.

                       

Problema
Invertir una lista enlazada significa cambiar el orden de los nodos de la lista, de tal forma que los que estaban al final ahora están al inicio y viceversa.

El primer nodo se vuelve el último, el segundo el penúltimo y el que originalmente era el último, ahora se vuelve el primero.


        
Pasos para realizar el ejercicio:
1.-  Se inicializan tres punteros: anterior, actual y temporal. 
        
✅Anterior y Temporal: Apuntan a null inicialmente y serán los encargados de gestionar el intercambio de las posiciones de los nodos de la lista.
    
✅Actual: Apunta al primer nodo de la lista original y es el encargado de establecer el puntero que se evalúa.
        
2.- Se recorre toda la lista hasta el final utilizando el puntero Actual y se almacena el siguiente nodo de la lista en el puntero temporal.
        
3.- La siguiente posición del puntero Actual, ahora será la posición del puntero Anterior.
        
4.- Se asigna el puntero Anterior a la posición de Actual.

5.- Se asigna el puntero Actual a la posición de Temporal.
           
6.- Se devuelve el puntero Anterior, que ahora es la cabeza de la lista invertida.

Presentación

Código en Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
 
     /**
     * Reverses a linked list.
     *
     * @param head the head of the linked list
     * @return the head of the reversed linked list
     */
    public ListNode reverseList(ListNode head) {
        ListNode anterior = null;
        ListNode actual = head;
        ListNode temporal = null;
 
        while (actual != null) {
            temporal = actual.next;
            actual.next = anterior;
            anterior = actual;
            actual = temporal;
        }
 
        return anterior;
    }
}

Código en php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
 
  /**
   * @param ListNode $head
   * @return ListNode
   */
  function reverseList($head) {
 
    //paso#1
    $anterior = null;
    $actual = $head;
    $temporal = null;
 
    while ($actual !== null) { 
      //paso#2
      $temporal = $actual->next;
      //paso #3
      $actual->next = $anterior;
 
      //paso#4
      $anterior = $actual;
 
      //paso#5
      $actual = $temporal;
    }
 
    //paso#6
    return $anterior;
  }
}
 

Código en Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        anterior = None
        actual = head
        temporal = None
 
        while actual is not None:
            temporal = actual.next
            actual.next = anterior
            anterior = actual
            actual = temporal
 
        return anterior
 

Código en C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // paso #1
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next = nullptr;
 
    while (curr != nullptr) {
      // paso #2
      next = curr->next;
      // paso #3
      curr->next = prev;
      // paso #4
      prev = curr;
      // paso #5
      curr = next;
    }
 
    // paso #6
    return prev;
    }
};

Código en JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // Paso #1
    let prev = null;
    let curr = head;
    let next = null;
 
    // Paso #2
    while (curr !== null) {
      // Paso #3
      next = curr.next;
      // Paso #4
      curr.next = prev;
      // Paso #5
      prev = curr;
      // Paso #6
      curr = next;
    }
 
    // Paso #7
    return prev;
};

        
    
Conclusión
En este artículo, aprendiste a invertir una lista enlazada. Este es un problema de programación común que se puede encontrar en entrevistas de trabajo, como las de Facebook.

La solución presentada en este artículo utiliza un puntero auxiliar para recorrer la lista enlazada en orden inverso. Esta solución es simple y eficiente, con una complejidad temporal de O(n) y una complejidad espacial de O(1).