0002. Add Two Numbers

Medium | Linked List + Math | 52 ms (94.00%), 13.6 MB (45.02%)

❓ Problem Statement

Source: LeetCode - Add Two Numbers GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

💡 Ideas

Note that two numbers might have different numbers of digits, so we need to take care of two linked lists with unequal lengths.

For each iteration, we need to check whether either l1 or l2 arrives at the end.

🤖 Python3

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur   = ListNode()
        ret   = cur
        carry = 0
        
        # ==================================================
        #  Linked List + Math                              =
        # ==================================================
        # time  : O(max(n, m))
        # space : O(1)
        
        while l1 or l2:
            if l1: 
                num1 = l1.val
                l1 = l1.next
            else: 
                num1 = 0
                
            if l2: 
                num2 = l2.val
                l2 = l2.next
            else: 
                num2 = 0
            
            val      = num1 + num2 + carry
            carry    = val // 10
            cur.next = ListNode(val % 10)
            cur      = cur.next
        
        # check carry to see if need to create extra node
        if carry != 0: cur.next = ListNode(carry)
            
        return ret.next

🤖 Java