DIY: Add Two Numbers II

Problem statement

Given two non-empty linked lists representing two non-negative integers, you have to add the two numbers and return the sum as a linked list. The digits are stored in such a way that the most significant digit comes first, and each of their nodes contains a single digit.

You may assume 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 2 linked lists as inputs containing non-negative integers in such a way that the heads of the linked lists contain the most significant digits. The following is an example of input:

// Sample Example - 1
3 -> 4 -> 6
2 -> 8 -> 1

// Sample Example - 2
1 -> 7 -> 9 -> 2
     2 -> 8 -> 1

Output

The function should return the sum of the input linked lists in another linked list.

// Sample Example - 1
6 -> 2 -> 7

// Sample Example - 2
2 -> 0 -> 7 -> 3

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 as another linked list as output.