Add Two Numbers

Table de matières

• Introduction
• Énoncé du problème
• Première solution
• Deuxième solution
• Comparaison
• Conclusion

Introduction

Dans cet article, je vais résoudre le problème de l’addition de deux nombres représentés sous forme de listes chaînées.

L’objectif est de proposer deux méthodes de résolution. La première sera volontairement moins efficace, tandis que la deuxième sera optimisée.

Enfin, une comparaison entre les deux méthodes sera effectuée.

Selon le site LeetCode, la difficulté de ce problème est moyenne.

Énoncé du problème

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Contraintes :

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Première solution

Dans cette méthode, nous explorons une approche directe. Elle repose sur l’extraction des valeurs des chiffres de chaque nombre, tout en évitant le déréférencement de pointeurs nuls et les problèmes de fuites mémoire.

Par exemple, retourner head->next sans libérer l’objet pointé par head entraînerait une fuite de mémoire.

Les conditions d’arrêt de l’algorithme sont les suivantes :

• Les deux pointeurs vers les listes de chiffres sont nuls.
• La retenue issue de l’addition est nulle.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(), *p = head;
        int res = 0, mod, div = 0, a, b, c;
        bool logic = (l1) || (l2) || div;
        while (logic)
        {
            a = l1 != nullptr ? l1->val : 0;
            b = l2 != nullptr ? l2->val : 0;
            c = a + b + div;
            mod = c % 10;
            p->val = mod;
            div = c / 10;
            l1 = l1 != nullptr ? l1->next : nullptr;
            l2 = l2 != nullptr ? l2->next : nullptr;
            logic = (l1) || (l2) || div;
            p->next = logic ? new ListNode() : nullptr;
            p = p->next;
        }
        return head;
    }
};

Deuxième solution

Les conditions algorithmiques sont identiques à celles de la première solution. La principale différence réside dans le regroupement des affectations conditionnelles dans un seul bloc.

Cette approche permet de mieux contrôler la gestion de la mémoire et de s’assurer que les ressources sont correctement libérées. En particulier, la suppression explicite du pointeur head évite toute fuite mémoire.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(), *p = head;
        int res = 0, mod, div = 0, a, b, c;
        bool logic = (l1) || (l2) || div;
        while (logic)
        {
            p->next = new ListNode();
            p = p->next;
            if (l1 != nullptr)
            {
                a = l1->val;
                l1 = l1->next;
            }
            else
            {
                a = 0;
                l1 = nullptr;
            }
            if (l2 != nullptr)
            {
                b = l2->val;
                l2 = l2->next;
            }
            else
            {
                b = 0;
                l2 = nullptr;
            }
            c = a + b + div;
            mod = c % 10;
            p->val = mod;
            div = c / 10;
            logic = (l1) || (l2) || div;
        }
        p = head->next;
        delete head;
        return p;
    }
};

Comparaison

Selon les conditions de test de la plateforme LeetCode, la première solution s’exécute en environ 7 ms pour l’ensemble des cas de test, tandis que la seconde s’exécute en moins d’une milliseconde.

Les deux solutions ne génèrent aucune fuite de mémoire.

Conclusion

Ce problème illustre clairement que la structuration du code a une influence significative sur le temps d’exécution ainsi que sur la taille de l’exécutable.

Il est également important de noter que les opérations d’allocation dynamique de mémoire sont coûteuses en temps d’exécution par rapport aux simples opérations arithmétiques.