Suma de gemelos de una lista enlazada

                
Suma máxima de gemelos de una lista enlazada (Java, Python, PHP, C++, Javascript)

Introducción
En este artículo, aprenderás a resolver un problema de programación común en entrevistas de Google: calcular el máximo par de sumas en una lista enlazada.

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 problema es una buena oportunidad para poner a prueba tus habilidades sobre listas enlazadas y algoritmos. Si puedes resolverlo de forma rápida y eficiente, serás un muy buen candidato en las entrevistas de Google.



Problema
El ejercicio consiste en encontrar la suma máxima de pares de nodos en su posición gemelo en una lista enlazada. 

Las posiciones gemelo cumplen la condición de, dado una posición i, se tendrá la posición  n-1-i donde:

    ✅ n es el total de elementos de la lista
    ✅ I es la posición actual del nodo.


        
Como se puede apreciar en el ejemplo, la posición 0 es gemela de la posición 3,
Ya que el tamaño total de la lista es 4 y la posición actual es 0, así que, se realiza el cálculo que en este caso  es 4-1-0 y da como resultado 3, su posición gemela.

Igualmente para para la posición 1, ya que 4-1-1 es 2, osea el siguiente nodo y su posición gemela

Pasos para realizar el ejercicio:
1.- Contar todos los elementos de la lista.

¿Cómo se hace? Establecemos un puntero extra, que llegue hasta el final de la lista, y por cada nodo, sumarlo a una variable llamada n.

2.- Inicializar un array y este permitirá guardar los valores que serán sumados.

3.- En la primera mitad de la lista guardar los valores de los nodos en el array en su posición de gemelo(n-1-i)

4.- Con la segunda mitad de la lista, sumarles los valores de los nodos a su posición 

5.- Devolver el mayor valor del array
            

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 int pairSum(ListNode head) {
        // Step #1
        int n = 0;
        ListNode aux = head;
        while (aux != null) {
            n++;
            aux = aux.next;
        }
 
        // Step #2
        Map<Integer, Integer> hm = new HashMap<>();
 
        // Step #3
        for (int i = 0; i < n / 2; i++) {
            hm.put(n - 1 - i, head.val);
            head = head.next;
        }
 
        // Step #4
        for (int i = n / 2; i < n; i++) {
            hm.put(i, hm.get(i) + head.val);
            head = head.next;
        }
 
        // Step #5
        return Collections.max(hm.values());
    }
}
 

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 Integer
     */
    function pairSum($head) {
        //Paso #1
        $n=0;
        $aux=$head;
 
        while($aux){
            $n++;
            $aux=$aux->next;
        }
 
        //Paso #2
        $hm=array();
 
        //Paso #3
        for ($i = 0; $i < $n/2; $i++) {
            $hm[$n-1-$i]=$head->val;
            $head=$head->next;
        }   
 
        //Paso #4
        for ($i; $i<$n;$i++){
            $hm[$i]=$hm[$i]+$head->val;
            $head=$head->next;
        }
 
        //Paso #5
        return max($hm);
    }
}

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:
    def pairSum(self, head):
        #paso #1
        n = 0
        aux = head
        while aux:
            n += 1
            aux = aux.next
 
        #paso #2
        hm = {}
 
        #paso #3
        for i in range(n // 2):
            hm[n - 1 - i] = head.val
            head = head.next
 
        #paso #4
        for i in range(n // 2, n):
            hm[i] = hm[i] + head.val
            head = head.next
 
        #paso #5
        return max(hm.values())

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:
  int pairSum(ListNode* head) {
    // Paso #1
    int n = 0;
    ListNode* aux = head;
    while (aux != nullptr) {
      n++;
      aux = aux->next;
    }
 
    // Paso #2
    std::vector<int> hm(n);
 
    // Paso #3
    for (int i = 0; i < n / 2; i++) {
      hm[n - 1 - i] = head->val;
      head = head->next;
    }
 
    // Paso #4
    for (int i = n / 2; i < n; i++) {
      hm[i] = hm[i] + head->val;
      head = head->next;
    }
 
    // Paso #5
    return *std::max_element(hm.begin(), hm.end());
  }
};

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 {number}
 */
var pairSum = function(head) {
      // Paso #1
    let n = 0;
    let aux = head;
 
    while (aux) {
      n++;
      aux = aux.next;
    }
 
    // Paso #2
    const hm = {};
 
    // Paso #3
    for (let i = 0; i < n / 2; i++) {
      hm[n - 1 - i] = head.val;
      head = head.next;
    }
 
    // Paso #4
    for (let i = n / 2; i < n; i++) {
      hm[i] = hm[i] + head.val;
      head = head.next;
    }
 
    // Paso #5
    return Math.max(...Object.values(hm));
};

        
    
Conclusión
En este artículo, aprendiste a resolver un problema de programación común en entrevistas de Google: calcular el máximo par de sumas en una lista enlazada.

En este caso, se utilizó una solución que utiliza hashmaps para almacenar las sumas de los pares de nodos adyacentes. Esta solución tiene una complejidad temporal de O(n) y una complejidad espacial de O(n).