Additionner deux grands nombres représentés sous forme de listes chaînées sans inverser les listes chaînées.

Question

Supposons que vous ayez 2 grands nombres représentés sous forme de listes chaînées, comment les additionner et stocker le résultat dans une liste chaînée séparée. Par exemple,

a = 2 -> 1 -> 7 
b = 3 -> 4
result = 2 -> 5 -> 1

Pouvez-vous les ajouter sans inverser les listes liées

Answer 1

Pseudocode :
Étape 1. Traversez les listes liées et poussez les éléments dans deux piles différentes.
Étape 2. Retirez les éléments supérieurs des deux piles
Étape 3. Additionnez les éléments (+ toute retenue provenant des additions précédentes) et stockez la retenue dans une variable temporaire.
Étape 4. Créez un nœud avec la somme et insérez-le au début de la liste des résultats.

Answer 2

Je pense que c'est quelque chose qui dépasse le contexte mais qui peut être très incitatif pour la personne qui a posté cette question à l'origine.

Voici donc une recommandation :

au lieu d'utiliser chaque nœud comme un chiffre unique du nombre, utilisez chaque nœud pour stocker un grand nombre (proche de la taille de l'entier) et si le plus grand nombre possible que vous avez choisi de stocker dans chaque nœud est x (dans votre cas 9), alors vous pouvez considérer votre nombre comme une représentation en base x+1 . où chaque chiffre est un nombre compris entre 0 et x.

Vous obtiendrez ainsi un gain de performance significatif, car l'algorithme s'exécutera en O(log n) et nécessitera le même nombre de nœuds, contre O(n) dans votre cas, n étant le nombre de chiffres décimaux de la plus grande des deux additions.

En général, pour faciliter votre algorithme, vous pouvez choisir une puissance de 10 comme base qui s'inscrit dans l'intervalle de votre nombre entier.

Par exemple, si votre nombre est 1234567890987654321 et que vous voulez le stocker dans une liste liée en choisissant la base 10^8, votre représentation devrait ressembler à ceci :

87654321-> 4567890 -> 123(little endian)

Answer 3

Voici ma tentative en Java qui fonctionne en environ O(max(len(a),len(b))). J'ai fourni un exemple complet avec une implémentation très simple de liste singulièrement liée. Il est assez tard ici et le code n'est pas aussi beau que je l'aurais souhaité - désolé !

Ce code suppose :

• Que la longueur des listes est connue
• Liste singulièrement liée
• Traitement des données entières

Il utilise la récursion pour propager les sommes et les retenues pour chaque chiffre, et additionne de gauche à droite. Les listes ne sont jamais inversées - les sommes sont effectuées de gauche à droite, et la retenue se propage dans la pile récursive. Elle pourrait être déroulée dans une solution itérative, mais je ne m'en préoccuperai pas.

public class LinkedListSum {
    static class LLNode {
        int value;
        LLNode next;
        public LLNode(int value){
            this.value = value;
        }
        public int length(){
            LLNode node = this;
            int count = 0;
            do {
                count++;
            } while((node = node.next) != null);
            return count;
        }
        public List<Integer> toList(){
            List<Integer> res = new ArrayList<Integer>();
            LLNode node = this;
            while(node != null){
                res.add(node.value);
                node = node.next;
            }
            return res;
        }
    }

    public static void main(String[] argc){
        LLNode list_a = fromArray(new int[]{4,7,4,7});
        LLNode list_b = fromArray(new int[]{5,3,7,4,7,4});
        System.out.println("Sum: " + sum(list_a, list_b).toList());
    }

    private static LLNode fromArray(int[] arr){
        LLNode res = new LLNode(0);
        LLNode current = res;
        for(int i = 0; i < arr.length; i++){
            LLNode node = new LLNode(arr[i]);
            current.next = node;
            current = node;
        }
        return res.next;
    }

    private static LLNode sum(LLNode list_1, LLNode list_2){
        LLNode longer;
        LLNode shorter;
        if(list_1.length() >= list_2.length()){
            longer = list_1;
            shorter = list_2;
        } else {
            longer = list_2;
            shorter = list_1;
        }

        // Pad short to same length as long
        int diff = longer.length() - shorter.length();
        for(int i = 0; i < diff; i++){
            LLNode temp = new LLNode(0);
            temp.next = shorter;
            shorter = temp;
        }

        System.out.println("Longer: " + longer.toList());
        System.out.println("Shorter: " + shorter.toList());

        return sum_same_length(new LLNode(0), null, longer, shorter);
    }

    private static LLNode sum_same_length(LLNode current, LLNode previous, LLNode longerList, LLNode shorterList){
        LLNode result = current;
        if(longerList == null){
            previous.next = null;
            return result;
        }

        int sum = longerList.value + shorterList.value;
        int first_value = sum % 10;
        int first_carry = sum / 10;
        current.value = first_value;

        // Propagate the carry backwards - increase next multiple of 10 if necessary
        LLNode root = propagateCarry(current,previous,first_carry);

        current.next = new LLNode(0);
        sum_same_length(current.next, current, longerList.next, shorterList.next);

        // Propagate the carry backwards - increase next multiple of 10 if necessary:
        // The current value could have been increased during the recursive call
        int second_value = current.value % 10;
        int second_carry = current.value / 10;
        current.value = second_value;

        root = propagateCarry(current,previous,second_carry);
        if(root != null) result = root;

        return result;
    }

    // Returns the new root of the linked list if one had to be added (due to carry)
    private static LLNode propagateCarry(LLNode current, LLNode previous, int carry){
        LLNode result = null;
        if(carry != 0){
            if(previous != null){
                previous.value += carry;
            } else {
                LLNode first = new LLNode(carry);
                first.next = current;
                result = first;
            }
        }
        return result;
    }
}

Answer 4

Voici un pseudo-code.

list *add (list *l1, list *l2)
{
  node *l3, l3_old;

  while (l1 != NULL)
  {
    stack1.push (l1);
    l1 = l1->next;
  }
  while (l2 != NULL)
  {
    stack2.push (l2);
    l2 = l2->next;
  }

  l3_old = NULL;
  while (!stack1.isempty () && !stack2.isempty ()) // at least one stack is not empty
  {
    l3 = get_new_node ();
    l1 = stack1.pop ();
    l2 = stack2.pop ();
    l3->val = l1->val + l2->val;
    if (l3_old != NULL)
    {
      l3->val = l3->val + (int)l3_old/10;
      l3_old->val %= 10;
    }
    l3->next = l3_old;
    l3_old = l3;
  }
  while (!stack1.isempty ())
  {
    l1 = stack1.pop ();
    l3 = get_new_node ();
    l3->val = l1->val + (int)l3_old->val/10;
    l3_old->val %= 10;
    l3->next = l3_old;
    l3_old = l3;
  }
  while (!stack2.isempty ())
  {
    l2 = stack2.pop ();
    l3 = get_new_node ();
    l3->val = l2->val + (int)l3_old->val/10;
    l3_old->val %= 10;
    l3->next = l3_old;
    l3_old = l3;
  }
  return l3;
}

Answer 5

Voici ma tentative, en utilisant les deux listes liées et en retournant la somme comme une nouvelle liste en utilisant la récursion.

public class SumList {

int[] a1= {7,3,2,8};
int[] a2= {4,6,8,4};
LinkedList l1= new LinkedList(a1);
LinkedList l2= new LinkedList(a2);
Node num1= l1.createList();
Node num2= l2.createList();
Node result;

public static void main(String[] args) {
    SumList sl= new SumList();
    int c= sl.sum(sl.num1, sl.num2);
    if(c>0) {
        Node temp= new Node(c);
        temp.next= sl.result;
        sl.result= temp;
    }

    while(sl.result != null){
        System.out.print(sl.result.data);
        sl.result= sl.result.next;
    }
}

int sum(Node n1, Node n2) {
    if(n1==null || n2==null)
        return 0;
    int a1= this.getSize(n1);
    int a2= this.getSize(n2);
    int carry, s= 0;
    if(a1>a2) {
        carry= sum(n1.next, n2);
        s= n1.data+carry;
    }
    else if(a2>a1) {
        carry= sum(n1, n2.next);
        s= n2.data+carry;
    }
    else {
        carry= sum(n1.next, n2.next);
        s= n1.data+n2.data+carry;
    }
    carry= s/10;
    s=s%10;

    Node temp= new Node(s);
    temp.next= result;
    result= temp;

    return carry;
}

int getSize(Node n) {
    int count =0;
    while(n!=null) {
        n=n.next;
        count++;
    }
    return count;
}
}