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

Essayez ceci

/* No Recursion, No Reversal - Java */

import java.util.*;

class LinkedListAddMSB
{
  static LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
  {
    LinkedList<Integer> res = new LinkedList<Integer>();
    LinkedList<Integer> shorter = new LinkedList<Integer>();
    LinkedList<Integer> longer = new LinkedList<Integer>();
    int carry = 0;
    int maxlen,minlen;
    if(num1.size() >= num2.size())
    {
        maxlen = num1.size();
        minlen = num2.size();
        shorter = num2;
        longer = num1;
    }
    else
    {
        maxlen = num2.size();
        minlen = num1.size();
        shorter = num1;
        longer = num2;
    }

    //Pad shorter list to same length by adding preceeding 0
    int diff = maxlen - minlen;
    for(int i=0; i<diff; i++)
    {
        shorter.addFirst(0);
    }

    for(int i=maxlen-1; i>=0; i--)
    {
        int temp1 = longer.get(i);
        int temp2 = shorter.get(i);
        int temp3 = temp1 + temp2 + carry;
        carry = 0;

        if(temp3 >= 10)
        {
            carry = (temp3/10)%10;
            temp3 = temp3%10;
        }
        res.addFirst(temp3);
    }

    if(carry > 0)
        res.addFirst(carry);

    return res;
}

public static void main(String args[])
{
    LinkedList<Integer> num1 = new LinkedList<Integer>();
    LinkedList<Integer> num2 = new LinkedList<Integer>();
    LinkedList<Integer> res = new LinkedList<Integer>();
    //64957
    num1.add(6);
    num1.add(4);
    num1.add(9);
    num1.add(5);
    num1.add(7);

    System.out.println("First Number: " + num1);

    //48
    num2.add(4);
    num2.add(8);

    System.out.println("First Number: " + num2);

    res = addList(num1,num2);
    System.out.println("Result: " + res);
  }
}

Answer 2

/* this baby does not reverse the list
** , it does use recursion, and it uses a scratch array */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct list {
    struct list *next;
    unsigned value;
    };

unsigned recurse( char target[], struct list *lp);
struct list * grab ( char buff[], size_t len);

unsigned recurse( char target[], struct list *lp)
{
    unsigned pos;
    if (!lp) return 0;
    pos = recurse (target, lp->next);
    /* We should do a bounds check target[] here */
    target[pos] += lp->value;
    if (target[pos] >= 10) {
        target[pos+1] += target[pos] / 10;
        target[pos] %= 10;
        }
    return 1+pos;
}

struct list * grab ( char *buff, size_t len)
{
size_t idx;
struct list *ret, **hnd;

    /* Skip prefix of all zeros. */
    for (idx=len; idx--; ) {
        if (buff [idx] ) break;
        }
    if (idx >= len) return NULL;

    /* Build the result chain. Buffer has it's LSB at index=0,
    ** but we just found the MSB at index=idx.
    */
    ret = NULL; hnd = &ret;
    do {
        *hnd = malloc (sizeof **hnd);
        (*hnd)->value = buff[idx];
        (*hnd)->next = NULL;
        hnd = &(*hnd)->next;
        } while (idx--);

return ret;
}

int main (void)
{
    char array[10];
    struct list a[] = { {NULL, 2} , {NULL, 1} , {NULL, 7} };
    struct list b[] =             { {NULL, 3} , {NULL, 4} };
    struct list *result;

    a[0].next = &a[1]; a[1].next = &a[2];
    b[0].next = &b[1];

    memset(array, 0 , sizeof array );
    (void) recurse ( array, a);
    (void) recurse ( array, b);
    result = grab ( array, sizeof array );

    for ( ; result; result = result->next ) {
        printf( "-> %u" , result->value );
        }
    printf( "\n" );

return 0;
}

Answer 3

Version finale (pas d'inversion de liste, pas de récursion) :

#include <stdio.h>
#include <stdlib.h>

struct list {
        struct list *nxt;
        unsigned val;
        };

struct list *sumlist(struct list *l, struct list *r);
int difflen(struct list *l, struct list *r);

struct list *sumlist(struct list *l, struct list *r)
{
int carry,diff;
struct list *result= NULL, **pp = &result;

        /* If the lists have different lengths,
        ** the sum will start with the prefix of the longest list
        */
for (diff = difflen(l, r); diff; diff += (diff > 0) ? -1 : 1) {
        *pp = malloc (sizeof **pp) ;
        (*pp)->nxt = NULL;
        if (diff > 0) { (*pp)->val = l->val; l= l->nxt; }
        else { (*pp)->val = r->val; r= r->nxt; }
        pp = &(*pp)->nxt ;
        }

        /* Do the summing.
        ** whenever the sum is ten or larger we increment a carry counter
        */
for (carry=0; l && r; l=l->nxt, r=r->nxt) {
        *pp = malloc (sizeof **pp) ;
        (*pp)->nxt = NULL;
        (*pp)->val = l->val + r->val;
        if ((*pp)->val > 9) carry++;
        pp = &(*pp)->nxt ;
        }

        /* While there are any carries, we will need to propagate them.
        ** Because we cannot reverse the list (or walk it backward),
        ** this has to be done iteratively.
        ** Special case: if the first digit needs a carry,
        ** we have to insert a node in front of it
        */
for (diff =0    ;carry; carry = diff) {
        struct list *tmp;
        if (result && result->val > 9) {
                tmp = malloc(sizeof *tmp);
                tmp->nxt = result;
                tmp->val = 0;
                result = tmp;
                }
        diff=0;
        for (tmp=result; tmp ; tmp= tmp->nxt) {
                if (tmp->nxt && tmp->nxt->val > 9) {
                   tmp->val += tmp->nxt->val/10;
                   tmp->nxt->val %= 10; }
                if (tmp->val > 9) diff++;
                }
        }
return result;
}

int difflen(struct list *l, struct list *r)
{
int diff;

for (diff=0; l || r; l = (l)?l->nxt:l, r = (r)?r->nxt:r ) {
        if (l && r) continue;
        if (l) diff++; else diff--;
        }
return diff;
}

int main (void)
{
        struct list one[] = { {one+1, 2} , {one+2, 6} , {NULL, 7} };
        struct list two[] = { {two+1, 7} , {two+2, 3} , {NULL, 4} };
        struct list *result;

        result = sumlist(one, two);

        for ( ; result; result = result->nxt ) {
                printf( "-> %u" , result->val );
                }
        printf( ";\n" );

return 0;
}

Answer 4

En java, je vais le faire de cette façon

public class LLSum {
public static void main(String[] args) {
    LinkedList<Integer> ll1 = new LinkedList<Integer>();
    LinkedList<Integer> ll2 = new LinkedList<Integer>();

    ll1.add(7);
    ll1.add(5);
    ll1.add(9);
    ll1.add(4);
    ll1.add(6);

    ll2.add(8);
    ll2.add(4);

    System.out.println(addLists(ll1,ll2));
}
public static LinkedList<Integer> addLists(LinkedList<Integer> ll1, LinkedList<Integer> ll2){
    LinkedList<Integer> finalList = null;

    int num1 = makeNum(ll1);
    int num2 = makeNum(ll2);

    finalList = makeList(num1+num2);
    return finalList;
}
private static LinkedList<Integer> makeList(int num) {
    LinkedList<Integer> newList = new LinkedList<Integer>();

    int temp=1;
    while(num!=0){
        temp = num%10;
        newList.add(temp);
        num = num/10;
    }
    return newList;
}
private static int makeNum(LinkedList<Integer> ll) {
    int finalNum = 0;
    for(int i=0;i<ll.size();i++){
        finalNum += ll.get(i) * Math.pow(10,i);
    }
    return finalNum;
  }
}

Answer 5

Voici mon premier essai :

public class addTwo {
public static void main(String args[]){
    LinkedListNode m =new LinkedListNode(3);
    LinkedListNode n = new LinkedListNode(5);
    m.appendNew(1);
    m.appendNew(5);
    m.appendNew(5);
    n.appendNew(9);
    n.appendNew(2);
    n.appendNew(5);
    n.appendNew(9);
    n.appendNew(9 );
    m.print();
    n.print();
    LinkedListNode add=addTwo(m,n);
    add.print();

}

static LinkedListNode addTwo(LinkedListNode m,LinkedListNode n){
    LinkedListNode result;
    boolean flag =false;
    int num;
    num=m.data+n.data+(flag?1:0);
    flag=false;
    if(num>9){
        flag=true;
    }
    result = new LinkedListNode(num%10);
    while(m.link!=null && n.link!=null){
        m=m.link;
        n=n.link;
        num=m.data+n.data+(flag?1:0);
        flag=false;
        if(num>9){
            flag=true;
        }
        result.appendNew(num%10);
    }

    if(m.link==null && n.link==null){
        if(flag)
            result.appendNew(1);
        flag=false;
    }else if(m.link!=null){
        while(m.link !=null){
            m=m.link;
            num=m.data;
            num=m.data+(flag?1:0);
            flag=false;
            if(num>9){
                flag=true;
            }
            result.appendNew(num%10);
        }
    }else{
        while(n.link !=null){
            n=n.link;
            num=n.data;
            num=n.data+(flag?1:0);
            flag=false;
            if(num>9){
                flag=true;
            }
            result.appendNew(num%10);
        }
    }
    if(flag){
        result.appendNew(1);
    }

    return result;
}

class LinkedListNode {
public int data;
public LinkedListNode link;
public LinkedListNode(){System.out.println(this+":"+this.link+":"+this.data);}
public LinkedListNode(int data){
    this.data=data;
}
void appendNew(int data){
    if(this==null){
        System.out.println("this is null");
        LinkedListNode newNode = new LinkedListNode(data);
    }
    LinkedListNode newNode = new LinkedListNode(data);
    LinkedListNode prev =this;
    while(prev.link!=null){
        prev = prev.link;
    }
    prev.link=newNode;
}
void print(){
    LinkedListNode n=this;
    while(n.link!=null){
        System.out.print(n.data +"->");
        n = n.link;
    }
    System.out.println(n.data);
}
}

Le résultat est :

3->1->5->5

5->9->2->5->9->9

8->0->8->0->0->0->1