Intercambiar nodos en pares

Intercambiar nodos en pares (Java, Python, PHP, C++, Javascript).

Introducción
En este artículo, aprenderás cómo intercambiar nodos en pares en una lista enlazada. Este es un problema común en la programación, y es importante saber cómo resolverlo.

En una entrevista de Facebook, a menudo se te pedirá que resuelvas un problema de programación que implique listas enlazadas. Uno de los problemas más comunes es el problema de intercambiar nodos en pares.

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

Este ejercicio se encuentra en la plataforma de LeetCode como "Swap Nodes In Pairs".

           


Problema
Dada una lista enlazada, intercambie cada dos nodos adyacentes y devuelva su cabeza. 
                


Debe resolver el problema sin modificar los valores en los nodos de la lista (es decir, solo se pueden cambiar los nodos).

Pasos para realizar el algoritmo:
1.- Verificar que la lista enlazada tenga al menos un par de nodos, ya que si no los tiene no hay que cambiar de posición. 

2.- Establecer con un puntero, en este caso llamado home, el nuevo inicio de la lista. ¿Cuál sería este puntero? el siguiente al inicial de la lista

3.- Inicio de hacer el cambio de los pares. Para esto, inicializamos un puntero llamado end en la posición del puntero head.
Este será el encargado para más adelante unir los pares de nodos en la lista.

4.- Establecemos otro puntero auxiliar, que estará en la siguiente posición del puntero head y será el encargado de establecer el nodo inicial del cambio de los pares

5.- Asignamos que el siguiente nodo del puntero end sea el puntero aux, y esto es importante porque es el que conectará los pares de nodos de la lista más adelante.

NOTA: La primera vez que corre el programa el algoritmo no realiza nada porque ya está bien estructurado.

6.- Asignamos que la siguiente posición del puntero head sea la siguiente posición del puntero aux.

7- Asignamos que la siguiente posición del puntero aux sea el puntero head

8.- Establecemos que el puntero end apunte al nodo head, por los momentos no se ve relevante, pero gracias a esto se conectaran los pares de punteros más adelante.

9.- Establecemos que el puntero head pase a su posición siguiente

            

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 {
 
    public static ListNode swapPairs(ListNode head) {
        // paso #1
        if (head == null || head.next == null) {
            return head;
        }
 
        // paso #2
        ListNode home = head.next;
 
        // paso #3
        ListNode end = head;
 
        while (head != null && head.next != null) {
            // Pasos para voltear los pares de nodos
            ListNode aux = head.next; // paso #4
            end.next = aux; // paso #5
            head.next = aux.next; // paso #6
            aux.next = head; // paso #7
 
            // Pasos para actualizar los punteros
            end = head; // paso #8
            head = head.next; // paso #9
        }
 
        // retornamos el puntero home
        return home;
    }
}

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 swapPairs($head) {
        //paso #1
        if(!$head->next || !$head) return $head;
 
        //paso #2
        $home=$head->next;
 
        //paso #3
        $end=$head;
 
        while ($head->next){
 
            //Pasos para voltear los pares de nodos
            $aux=$head->next;           //paso #4
            $end->next=$aux;            //paso #5
            $head->next=$aux->next;     //paso #6
            $aux->next=$head;           //paso #7
 
            //Pasos para actualizar los punteros
            $end=$head;                 //paso #8
            $head=$head->next;          //paso #9
        }
 
        //retornamos el puntero home
        return $home;
    }
}

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 swapPairs(self, head):
        # paso #1
        if head is None or head.next is None:
            return head
 
        # paso #2
        home = head.next
 
        # paso #3
        end = head
 
        while head and head.next:
            # Pasos para voltear los pares de nodos
            aux = head.next           # paso #4
            end.next = aux            # paso #5
            head.next = aux.next     # paso #6
            aux.next = head           # paso #7
 
            # Pasos para actualizar los punteros
            end = head                 # paso #8
            head = head.next          # paso #9
 
        # retornamos el puntero home
        return home

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* swapPairs(ListNode* head) {
    // paso #1
    if (!head || !head->next) return head;
 
    // paso #2
    ListNode* home = head->next;
 
    // paso #3
    ListNode* end = head;
 
    while (head && head->next) {
      // Pasos para voltear los pares de nodos
      ListNode* aux = head->next; // paso #4
      end->next = aux; // paso #5
      head->next = aux->next; // paso #6
      aux->next = head; // paso #7
 
      // Pasos para actualizar los punteros
      end = head; // paso #8
      head = head->next; // paso #9
    }
 
    // retornamos el puntero home
    return home;
  }
};

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 swapPairs = function(head) {
        // paso #1
    if (!head || !head.next) return head;
 
    // paso #2
    const home = head.next;
 
    // paso #3
    let end = head;
 
    while (head && head.next) {
      // Pasos para voltear los pares de nodos
      const aux = head.next; // paso #4
      end.next = aux; // paso #5
      head.next = aux.next; // paso #6
      aux.next = head; // paso #7
 
      // Pasos para actualizar los punteros
      end = head; // paso #8
      head = head.next; // paso #9
    }
 
    // retornamos el puntero home
    return home;
};

        
        
Conclusión
Intercambiar nodos en pares en una lista enlazada es un problema de programación relativamente sencillo. Al usar dos punteros, podemos intercambiar los valores de los dos nodos de forma eficiente.