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

Mon implémentation récursive en Java :

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwoNumbers(l1, l2, 0);
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2, int carryOver) {
        int result; 
        ListNode next = null;

        if (l1 == null && l2 == null) {
            if (carryOver > 0) {
                return new ListNode(carryOver);
            } else {
                return null;            
            }
        } else if (l1 == null && l2 != null) {
            result = l2.val + carryOver;  
            next = addTwoNumbers(null, l2.next, result / 10);            
        } else if (l1 != null && l2 == null){
            result = l1.val + carryOver;
            next = addTwoNumbers(l1.next, null, result / 10);
        } else {
            result = l1.val + l2.val + carryOver;            
            next = addTwoNumbers(l1.next, l2.next, result / 10);
        }

        ListNode node = new ListNode(result % 10);
        node.next = next;

        return node;
    }
}

J'espère que cela vous aidera.

Answer 2

/* spoiler : une simple récursion suffira */

#include <stdio.h>

struct list {
    struct list *next;
    unsigned value;
    };
struct list a[] = { {NULL, 2} , {NULL, 1} , {NULL, 7} };
struct list b[] = { {NULL, 3} , {NULL, 4} };

unsigned recurse( unsigned * target, struct list *lp);
unsigned recurse( unsigned * target, struct list *lp)
{
    unsigned fact;
    if (!lp) return 1;
    fact = recurse (target, lp->next);

    *target += fact * lp->value;
    return 10*fact;
}

int main (void)
{
    unsigned result=0;

    /* set up the links */
    a[0].next = &a[1];
    a[1].next = &a[2];
    b[0].next = &b[1];

    (void) recurse ( &result, a);
    (void) recurse ( &result, b);

    printf( "Result = %u\n" , result );

return 0;
}