Cet article fait partie d'une série commencée ici :

. N'hésitez pas à lire l'introduction pour en savoir plus sur les algorithmes. 

 

 

Paramètres: N°1: (2 -> 4 -> 3) + N°2: (5 -> 6 -> 4)

Application du `reverse-order` : (243 -> 342) + (564 -> 465 )= 807

Retour `linked-list` : (7 -> 0 -> 8)

 

Paramètres:  N°1: (1) + N°2: (9 -> 9)

Application `reverse-order` : (1 -> 1) + (99 -> 99) = 100

Retour `linked-list` : (0 -> 0 -> 1)

 

Cette description permet de retenir quatre points plus ou moins utiles :

Une `linked-list` ou `liste chaînée` en français est une structure de données qui à un nœud de départ contenant une valeur et un lien vers la valeur suivante. Nous utiliserons ici la version `simple` (un nœud pointe vers un seul nœud, toujours dans le même sens) mais la page Wikipédia pourra vous en dire plus. Ce qu'il est important de retenir sur cette structure :

Javascript n'offre pas cette structure de données en tant que telle mais on pourrait la représenter comme l'objet suivant :

const listeChainee = {
  valeur: 123,
  noeudSuivant: {
    valeur: "xyz",
    noeudSuivant: {
      valeur: false,
      noeudSuivant: {
        ...n
      }
    }
  }
}

Pour nous aider, Leetcode nous fournit dans la `sandbox` une fonction pour simuler ce comportement :

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

Voici la première version fonctionnelle à laquelle je suis parvenue est ci-dessous :

var addTwoNumbers = function(list1, list2) {
  //Initialisation de la List Chainée que nous allons retourner
  //const List = new ListNode(0);
  //Initialisation d'un curseur pour progresser dans la liste au fur et
  // à mesure des additions / noeuds
  let curseur = List;

  //Mon approche est récursive - nous verrons une seconde
  //approche dans la suite de ce post
  //Ma fonction récursive accepte deux noeuds et une retenu
  // La retenu étant la dizaine qu'il faudra répercuter sur le prochain calcul
  var recursive = function(list1, list2, retenu){
    
    //Si mes deux noeuds ont une valeur :
    if(list1 && list2){
      //Je les additionne avec la retenu
      var add = list1.val + list2.val + retenu;

      //Si mon addition est >= 10, elle ne sera pas acceptée dans
      // ma liste chainée.
      if(add >= 10) {
        //Je retiens 1, jamais plus car maxAdd = 9 + 9 = 18%10 = 1
        retenu = 1;
        //Je supprime de ma valeur le 10 que je viens de retenir
        add = add - 10
      }else {
        //Si mon addition est inférieure à 10, je n'ai plus besoin de retenir.
        retenu = 0;
      }

      //Je peux désormais ajouter le prochain maillon de ma chaine listée
      curseur.next = new ListNode(add);
      //Et faire progresser le curseur sur ce nouveau maillon avant
      // de poursuivre ma récursion
      curseur = curseur.next;
      //Je relance ma fonction avec les prochain noeuds de mes
      // paramètres et la nouvelle retenu
      return recursive(list1.next, list2.next, retenu);
    } else if(list1 && list2 === null) {
      //Si j'ai parcouru entièrement mon second paramètre, je n'ai
      // plus à l'inclure lors de l'addition
      var add = list1.val + retenu;
      //Le reste est similaire à la première condition...
      if(add >= 10) {
        retenu = 1;
        add = add - 10
      }else {
        retenu = 0;
      }

      curseur.next = new ListNode(add);
      curseur = curseur.next;
      //Mon second paramètre est désormais null
      return recursive(list1.next, null, retenu);
    } else if(list1 === null && list2) {
      //Idem que la boucle précédente mais dans le cas ou le
      // premier paramètre s'épuise avant le second
      var add = list2.val + retenu;
      if(add >= 10) {
        retenu = 1;
        add = add - 10
      }else {
        retenu = 0;
      }
      
      curseur.next = new ListNode(add);
      curseur = curseur.next;
      return recursive(null, list2.next, retenu);
    } else {
      //Dans le cas ou j'ai (enfin) parcouru mes deux paramètres :
      //Je rajoute un noeud s'il me reste une retenu depuis la
      // précédente addition - Case [5][5]
      if(retenu !== 0) {
        curseur.next = new ListNode(retenu)
      }
      console.log('Done ;-)');
      //Peu importe la valeur de retour ici
      return true;
    }
  }
  
  //J'initialise ma fonction récursive avec mes deux paramètres et
  // une retenu valant par défaut 0
  recursive(list1, list2, 0);

  //Je retourne une liste chainée A PARTIR du second noeud - le
  // premier noeud étant une simple initialisation
  return List.next;
};

Un code fonctionnel mais qui peut être re-factorisé pour être au moins plus agréable à travailler. La complexité est néanmoins bonne :

Leetcode met 380ms pour 1563 tests. Peut mieux faire.

Il suffit ensuite de refactoriser pour avoir un code plus simple et lisible :

const addTwoNumbers = function(l1, l2) {
  //L'initialisation ne change pas
  const List = new ListNode();
  let curseur = List;

  //Je défini une fonction qui va gérer le retenu
  //J'envoie le résultat de mon addition et je retourne la valeur de
  // mon noeud et de mon retenu
  const retenuHelper = add => {
    if (add > 9) return { add: add - 10, retenu: 1 };
    else return { add: add, retenu: 0 };
  };

  //Mon curseur étant une variable dans le scope principal, je peux
  // aussi avoir une fonction pour le déplacer
  const moveCurseur = add => {
    curseur.next = new ListNode(add);
    curseur = curseur.next;
  };

  //Ma fonction récursive est strictement identique, je ne fais 
  // qu'utiliser mes fonctions d'aide pour la rendre plus concise
  const recursive = (l1, l2, retenu) => {
    //Les conditions ne changent pas
    if (l1 && l2) {
      //Je  pourrai même regrouper retenuHelper() et moveCurseur() 
       // en une seule fonction mais cela me semble plus lisible
       // comme ceci. Refactoriser != Obfuscer
      var { add, retenu } = retenuHelper(l1.val + l2.val + retenu);
      moveCurseur(add);
      return recursive(l1.next, l2.next, retenu);
    } else if (l1 && l2 === null) {
      var { add, retenu } = retenuHelper(l1.val + retenu);
      moveCurseur(add);
      return recursive(l1.next, null, retenu);
    } else if (l1 === null && l2) {
      var { add, retenu } = retenuHelper((add = l2.val + retenu));
      moveCurseur(add);
      return recursive(null, l2.next, retenu);
    } else {
      if (retenu !== 0) curseur.next = new ListNode(retenu);
      return true;
    }
  };

  //init et retour ne changent pas
  recursive(l1, l2, 0);
  return List.next;
};

La même logique, écrite dans une philosophie plus Don't Repeat Yourself, met 116ms à être exécutée. Soit un gain de près de 70% ! C'est beaucoup mieux :-)

Pour chaque problème, Leetcode offre un espace de discussion où vous pouvez - après avoir essayé tout seul - voir ce qu'ont fait les autres, ce qui est toujours intéressant. Le code javascript le plus concis que j'ai trouvé parmi ces autres solutions est celui-ci :

function addTwoNumbers(l1, l2) {
  //Initialisation de la List à retourner
  const before = new ListNode();
  //Définition du pointer
  let tail = before;
  //Définition du carry (retenu)
  let c = 0;
  /*while(l1 || l2 || c) va s'exécuter tant que l'un de ses trois 
 paramètres sont vrais. Cela permet de s'épargner la récursion et 
 donc l'initialisation. while est très utilisé dans d'autres languages - 
 je n'ai pas l'habitude de m'en servir en Javascript. Peut-être à tord...*/
  while (l1 || l2 || c) {
    //Plutôt que de tester chaque noeud dans une condition - on
    // définit une valeur de 0 pour chaque ABSENCE de noeud
    const v1 = l1 ? l1.val : 0;
    const v2 = l2 ? l2.val : 0;
    //Tous nos noeuds étant définis, on peut les additionner avec la retenu
    const v = v1+v2+c;

    //Même principe que les codes précédents
    tail.next = new ListNode(v%10);
    tail = tail.next;
    c = v >= 10 ? 1 : 0;

    //On fait évoluer les curseurs de nos paramètres seulement s'ils
    // existent - smart
    l1 = l1&&l1.next;
    l2 = l2&&l2.next;
  }

  //idem
  return before.next;
}

Pour 1563 tests, cette version s'exécute en 112ms soit un gain d'a peine 3%. Néanmoins, le code est près de deux fois plus court (16 lignes contre 31), ce qui peut avoir son importance. Savoir lequel de cet extrait ou de ma version re-factorisée est meilleure vous appartient et cela dépendra principalement de vos habitudes de développement, de celles de vos collègues, bref, de l'ensemble du contexte dans lequel s'inscrit votre algorithme.

Pour les adeptes de C#, j'ai benchmarké deux solutions ici - beats 100% et là - simple solution. Les benchmarks sont de 204ms et 132ms - soit plus lent que Javascript. On arrive à un beau 19ms en Java par ici, 63ms en Python et 28ms en C++.

 

Inutile de préciser que ces valeurs ne doivent pas être prises pour un benchmark sérieux.

Si dans le Code v1.1 vous changez ce morceau de code (et la lecture qui est faite du retour évidemment) :

const retenuHelper = add => {
  if (add > 9) return { add: add - 10, retenu: 1 };
  else return { add: add, retenu: 0 };
};

par

const retenuHelper = add => {
  if (add > 9) return [add - 10, 1];
  else return [add, 0];
};

vous aurez une fonction de 27% plus lente.

 

Pourquoi ? Un indice, c'est lié à l'exploitation de deux structures de données fondamentalement différentes. Si vous le savez, à vos commentaires :)