You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in forward order, such that the 1's 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

Given 6->1->7 + 2->9->5. That is, 617 + 295.

Return 9->1->2. That is, 912.

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
/**
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/
public ListNode addLists2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}

l1 = reverse(l1);
l2 = reverse(l2);

int sum = 0;
ListNode dummy = new ListNode(-1);

while (l1 != null || l2 != null) {
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}

ListNode node = new ListNode(sum % 10);
dummy.next = node;

sum = sum / 10;
}

if (sum == 1) {
ListNode node = new ListNode(1);
node.next = dummy.next;

return node;
}

return dummy.next;
}

ListNode prev = null, current = head;

while (current != null) {
ListNode temp = current.next;
current.next = prev;
prev = current;
current = temp;
}

return prev;
}
}
``````

Hope this helps,
Michael