Algorithms
Add two number represented by Linked Lists
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (9 -> 9 -> 7) + (4 -> 3 -> 7)
Output: 1 -> 5 -> 3 -> 3
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;
ListNode tail = null;
int carry = 0;
while(l1 != null || l2 != null){
int a = (l1 != null) ? l1.val : 0;
int b = (l2 != null) ? l2.val : 0;
int sum = (a+b)+carry;
carry = sum/10;
ListNode node = new ListNode(sum%10);
if(result == null){
result = node;
tail = node;
}
else{
tail.next = node;
tail=node;
}
l1 = l1 != null ? l1.next : l1;
l2 = l2 != null ? l2.next : l2;
}
if(carry == 1){
ListNode node = new ListNode(1);
tail.next = node;
}
return result;
}
