DIY: Add Two Numbers

Problem statement

Given two non-empty linked lists that represent two non-negative integers, you have to add the two numbers and return the sum as a linked list. The digits are stored in reverse order, and each of their nodes contains a single digit.

Note: You may assume that the two numbers do not contain any leading zero, except the number 0 itself.

Constraints

1. The number of nodes in each linked list is in the range [1, 100].
2. 0 <= Node->val <= 9
3. It is guaranteed that the list represents a number that does not have leading zeros.

Input

The function will take two linked lists, which will contain non-negative integers in the reverse order, as inputs. The following is an example of an input:

3 -> 4 -> 6
2 -> 8 -> 1

Output

The function should return the sum of the two linked lists given above in another linked list.

5 -> 2 -> 8

You may want to take extra care for the following cases:

Test case	Explanation
list1 = [1, 2] list2 = [1, 3, 5]	When one list is longer than the other
list1 = [] list2 = [2, 4]	When one list is null, that is, the list is empty
list1 = [9, 9] list2 = [9, 9]	When the sum has an extra carry of one at the end

Coding exercise

In this coding exercise, you need to implement the addTwoNumbers(list1, list2) function, where list1 and list2 are pointers to the head nodes of the linked lists. The function should return the sum of the two linked lists in the form of another linked list, as output.