Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

Class Node:
    data (int)
    next (Node)

Input Format:

First Parameter - Node l1

Second Parameter - Node l2

Output Format:

Return the Node.

Example 1:

Input:
    4
    1 0 1 0
    4
    2 1 0 5
Output:
    3 1 1 5
Explanation:
    First node is 3 (1+2). Second node is 1 (0+1). Third node is 1 (1+0). Fourth node is 5 (0+5).

Example 2:

Input:
    4
    9 9 9 9
    4
    9 9 9 1
Output:
   1 9 9 9 0    
Explanation:
    Last node is 9+1, which is 10. Number is of two digits, so 1 is carried to the tens place and 0 becomes the last node. It adds to tens place (9+9) to become 19, again sending a carry to next node. Similarly, hundreds and thousands nodes become 9. Finally, a 1 is carried to the left to create an additional node.

Constraints:

• 0<= No. of nodes <=100
• 0<= Node.data <=9
• Expected Time Complexity: O(n)
• Expected Auxiliary Space: O(1)