## Wednesday, December 24, 2014

### Find the sum of numbers whose digits are represented by linked list entries. Output the result as a linked list.

Q. You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1st digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example

Input: (7 -> 1 -> 6) +  (5 -> 9 -> 2). That is, 617 + 295.
Output: 2 -> 1 -> 9. That is, 912.

Suppose the digits are stored in forward order. Repeat the above problem.

Example

Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295.
Output: 9 -> 1 -> 2. That is, 912.

Source:

```import java.util.Stack;

public class Code{
private static Stack<Integer> getDigits(int number){
Stack<Integer> stack = new Stack<>();
int t = 10;
while(number!=0){
int q  = number % t;
stack.push(q);
number = number / 10;
}
return stack;
}

int number = (int)p.value;
int i=10;
p = p.next;
while(p != null){
number += (int)p.value * i;
i *= 10;
p = p.next;
}
return number;
}

int number = getNumberReverseOrder(ll);
StringBuilder num = new StringBuilder();
num.append(Integer.toString(number));
num.reverse();
return Integer.parseInt(num.toString());
}

Stack<Integer> digits = getDigits(number);

while(true){
if(digits.isEmpty()) break;
}
return ll;
}

Stack<Integer> digits = getDigits(number);

while(true){
temp.value = digits.pop();
if(digits.isEmpty())break;
temp.next = ll.new Node();
temp = temp.next;
}
return ll;
}

public static void main(String[] args){
int n1 = 999;
int n2 = 773;

//Reverse Order Test
list2 = makeListForReverseOrder(n2),
result;
int sum = getNumberReverseOrder(list1)+getNumberReverseOrder(list2);
result = makeListForReverseOrder(sum);
System.out.println(result);

//Forward Order Test
list1 = makeListForForwardOrder(n1);
list2 = makeListForForwardOrder(n2);
sum = getNumberForwardOrder(list1)+getNumberForwardOrder(list2);
result = makeListForForwardOrder(sum);
System.out.println(result);
}
}

public class Node{
Node next;
T value;

Node(T value){this.value = value;}
Node(){}
}

while(t.next!=null){t = t.next;}
t.next = new Node(value);
}

public boolean isEmpty(){
}

@Override
public String toString(){
StringBuilder bf = new StringBuilder();
while(t!=null){
bf.append(t.value).append(" -> ");
t = t.next;
}
bf.delete(bf.length()-4, bf.length());
return bf.toString();
}
}```

Output:

2 -> 7 -> 7 -> 1
1 -> 7 -> 7 -> 2

Approach  #2

Compute the sum on-the-fly and build the list as digits are calculated.

In this case, care must be taken if the digit length of the numbers is different. Padding with extra zeroes is required.

Source:

```import java.util.Stack;

public class Code{

private static Stack<Integer> getDigits(int number){
Stack<Integer> stack = new Stack<>();
int t = 10;
while(number!=0){
int q  = number % t;
stack.push(q);
number = number / 10;
}
return stack;
}

//Method #2

System.out.println("list 1 = "+l1+"\nlist 2 = "+l2);
return result;
}

if(l1 == null){
return;
}
int sum = l1.value + l2.value + carry;
carry = sum/10;
if(l1.next == null && l2.next == null && sum < 10)carry = -1;
}

while(true){
n1p = n1;
n1 = n1.next;

if(n1 == null && n2!=null){
while(n2!= null && n2.next!=null){
n1 = l1.new Node(0);
n1p.next = n1;
n1p = n1;
n2 = n2.next;
}
break;
}

n2p = n2;
n2 = n2.next;

if(n2==null && n1!=null){
while(n1!=null){
n2 = l2.new Node(0);
n2p.next = n2;
n2p = n2;
n1 = n1.next;
}
break;
}

if(n1==null && n2==null)break;
}
}

while(true){
n1p = n1;
n1 = n1.next;

if(n1 == null && n2!=null){
while(n2!= null && n2.next!=null){
n2 = n2.next;
}
break;
}

n2p = n2;
n2 = n2.next;

if(n2==null && n1!=null){
while(n1!=null){
n1 = n1.next;
}
break;
}

if(n1==null && n2==null)break;
}
}

System.out.println("list 1 = "+l1+"\nlist 2 = "+l2);
return result;
}

if(l1 == null)return 0;

int sum = l1.value + l2.value + carry;
carry = sum / 10;
return carry;
}

}

Stack<Integer> digits = getDigits(number);

while(true){
if(digits.isEmpty()) break;
}
return ll;
}

Stack<Integer> digits = getDigits(number);

while(true){
temp.value = digits.pop();
if(digits.isEmpty())break;
temp.next = ll.new Node();
temp = temp.next;
}
return ll;
}

public static void main(String[] args){
int n1 = 99999;
int n2 = 999990999;

//Reverse Order Test
list2 = makeListForReverseOrder(n2),
result;

//Forward Order Test
list1 = makeListForForwardOrder(n1);
list2 = makeListForForwardOrder(n2);

}
}```

Output:

list 1 = 9 -> 9 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 0
list 2 = 9 -> 9 -> 9 -> 0 -> 9 -> 9 -> 9 -> 9 -> 9
8 -> 9 -> 9 -> 0 -> 9 -> 0 -> 0 -> 0 -> 0 -> 1

list 1 = 0 -> 0 -> 0 -> 0 -> 9 -> 9 -> 9 -> 9 -> 9
list 2 = 9 -> 9 -> 9 -> 9 -> 9 -> 0 -> 9 -> 9 -> 9
1 -> 0 -> 0 -> 0 -> 0 -> 9 -> 0 -> 9 -> 9 -> 8