0002. Add Two Numbers

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

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:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Input: l1 = [0], l2 = [0]
Output: [0]

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

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.

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

class Solution {
    /**  
     * @time  : O(max(n, m))
     * @space : O(1)
     */
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode();
        ListNode ret = cur;
        int carry = 0;
        
        while(l1 != null || l2 != null) {
            int num1, num2;
            
            if(l1 != null) {
                num1 = l1.val;
                l1 = l1.next;
            } else num1 = 0;
            
            if(l2 != null) {
                num2 = l2.val;
                l2 = l2.next;
            } else num2 = 0;
            
            int sum = num1 + num2 + carry;
            carry = sum / 10;
            sum = sum % 10;
            
            cur.next = new ListNode(sum);
            cur = cur.next;
        }
        
        if(carry != 0) cur.next = new ListNode(carry);
        return ret.next;
    }
}

Previous0020. Valid Parentheses Next0445. Add Two Numbers II

Last updated 4 years ago

Was this helpful?