# You are given two non-empty linked lists representing two non-negative integers. 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.
#
# You may assume the two numbers do not contain any leading zero, except the number 0 itself.
#
# Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
# Output: 7 -> 0 -> 8

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        else:
            carry_over = 0
            l1_pointer = l1
            l2_pointer = l2
            l3 = None
            l3_pointer = None
            while True:
                if l1_pointer is None and l2_pointer is None:
                    if carry_over == 0:
                        break
                    else:
                        interim_sum = carry_over
                elif l1_pointer is None:
                    interim_sum = l2_pointer.val + carry_over
                    l2_pointer = l2_pointer.next
                elif l2_pointer is None:
                    interim_sum = l1_pointer.val + carry_over
                    l1_pointer = l1_pointer.next
                else:
                    interim_sum = l1_pointer.val + l2_pointer.val + carry_over
                    l1_pointer = l1_pointer.next
                    l2_pointer = l2_pointer.next

                carry_over = interim_sum / 10
                value = interim_sum % 10
                if l3 is None:
                    l3 = ListNode(value)
                    l3_pointer = l3
                elif l3_pointer.next is None:
                    l3_pointer.next = ListNode(value)
                    l3_pointer = l3_pointer.next

        return l3

# Note:
# Add respective values and carry forward the tens place to next set of values
# Example: 243 + 564 => 2+5 = 7 carry=0, 4+6+0 = 0 carry=1, 3+4+1 = 8 carry 0
# Keep in mind that length of two list can be different
