Problema:
Considera di rappresentare un numero attraverso una lista semplice come quella implementata in un precedente post.
Ogni elemeneto della lista rappresenta una delle cifre del numero. Le cifre sono memorizzate nell’ordine inverso. Quindi il primo elemento della lista sara’ la cifra delle unita’.
Prese due liste che rappresentano due numeri a e b, ritornare una nuova lista che rappresenta il risultato a + b.
Inputs:
Due liste semplici di interi: a e b
Output:
Una lista semplice di interi
Esempio:
Inputs:
a: 6, 5, 4, 3, 2, 8, 7
b: 1, 5, 7, 8, 9, 1, 7, 4, 3, 4
Output:
7, 0, 2, 2, 2, 0, 5, 5, 2, 4
Infatti 7823456 + 4347198751 = 4255022207
Il mio ragionamento
Scorro simultaneamente elemento per elemento ed effettuo la somma considerando il riporto. Se una lista e’ piu’ lunga dell’altra considero semplicemente pari a zero il valore dell’elemento non presente. E’ importante ricordarsi di aggiungere un eventuale riporto finale.
La mia soluzione
public static SingleLinkedList Sum(SingleLinkedList a, SingleLinkedList b)
{
if (a == null) throw new ArgumentNullException("a");
if (b == null) throw new ArgumentNullException("b");
var result = new SingleLinkedList();
Node pa = a.head;
Node pb = b.head;
int carry = 0;
while (pa != null || pb != null)
{
int va = (pa == null) ? 0 : pa.Value;
int vb = (pb == null) ? 0 : pb.Value;
int sum = va + vb + carry;
carry = sum / 10;
sum = sum % 10;
result.AddLast(sum);
pa = pa != null ? pa.Next : pa;
pb = pb != null ? pb.Next : pb;
}
if (carry > 0) result.AddLast(carry);
return result;
}