# (LeetCode) 2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

###### Medium

##### Description
> 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 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.
##### Example
> Input: l1 = [2,4,3], l2 = [5,6,4]
> Output: [7,0,8]
> Explanation: 342 + 465 = 807.

##### Solution1

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

        head = ListNode(0)
        cur = head

        p = l1
        q = l2

        while p or q:

            x = p.val if p else 0
            y = q.val if q else 0
    
            sum = cur.val + x + y
            carry = int(sum/10)

            cur.val = sum % 10

            if p:
                p = p.next
            if q:
                q = q.next

            if p or q or carry > 0:
                cur.next = ListNode(carry)
                cur = cur.next

        return head

##### Solution2(Recursive)

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry:int=0) -> ListNode:

        node = ListNode(carry)

        x = l1
        y = l2

        if x:
            node.val += x.val
            x = x.next
        if y:
            node.val += y.val
            y = y.next

        c = int(node.val/10)
        node.val = node.val % 10

        if x or y or c > 0:
            node.next = self.addTwoNumbers(x,y,c)

        return node