This is quite easy if we represent the two integers with lists that have the least significant digit at the head, eg:
A = 123 -> 3,2,1
B = 45 -> 5,4
result = 168 -> 8,6,1
You can check the code and some tests on my Gist (LinkedListSumJTests):
/*
Given two lists representing integer numbers
with the least significant digit in the head position
return a new list containing the sum
*/
public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){
if(x == null && y == null) return null;
int carry = 0, curr = 0, val = 0;
SingleLinkedListNode result = null, n = null;
//keep going until we have data in either list and do not forget the last carry!
while(x != null || y != null || carry != 0){
curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry
val = curr % 10; //take only LSD
//track if we have a carry
carry = (curr >= 10) ? 1 : 0;
if(n == null){
n = new SingleLinkedListNode(val);
result = n;
}
else{
n.next = new SingleLinkedListNode(val);
n = n.next;
}
//move to next digit
if(x != null) x = x.next;
if(y != null) y = y.next;
}
return result;
}
No comments:
Post a Comment
With great power comes great responsibility