time O(N) space O(N)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # main idea: using two stack to store values of l1,l2 and add both lower digit to get updated carry
        st1, st2 = [], []
        while l1:
            st1.append(l1.val)
            l1 = l1.next
        while l2:
            st2.append(l2.val)
            l2 = l2.next
        carry = 0
        dummy = None
        while  st1 or st2 or carry:
            l1v = st1.pop() if st1 else 0
            l2v = st2.pop() if st2 else 0
            curSum = l1v + l2v + carry
            # create new higher bit node
            newNode = ListNode(curSum%10)
            # connect new node with old list head 
            newNode.next = dummy
            dummy = newNode
            carry = curSum //10 
        return dummy