LeetCode #2 Add Two Numbers

Posted on | Post modified | In , , , , , , , ,

Problem

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.

Example

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution1

Method: Iterative

Time Complexity: O(|m| + |n|)

Space Complexity: O(|m|) if |m| > |n| else O(|n|)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return l1 or l2
        
        head = l1
        carry = 0

        while l1 or l2:
            l2_val = 0
            if l2:
                l2_val = l2.val
            else:
                l2 = ListNode(0)

            l1.val = l1.val + l2_val + carry
            carry = 0

            if l1.val >= 10:
                carry = 1
                l1.val = l1.val - 10
            
            if not l1.next:
                if l2.next or carry == 1:
                    l1.next = ListNode(0)

            l1 = l1.next
            l2 = l2.next   
        
        return head

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return l1 or l2
        
        head = l1
        carry = 0

        while l1 or l2:
            l2_val = 0
            if l2:
                l2_val = l2.val
            else:
                l2 = ListNode(0)

            carry, l1.val = divmod(l1.val + l2_val + carry, 10)
            
            if not l1.next and (l2.next or carry == 1):
                l1.next = ListNode(0)

            l1 = l1.next
            l2 = l2.next   
        
        return head

Solution2

Method: Iterative

Time Complexity: O(|m| + |n|)

Space Complexity: O(|m| + |n|)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def addTwoNumbers(self, l1, l2):
    carry = 0
    root = n = ListNode(0)
    while l1 or l2 or carry:
        v1 = v2 = 0
        if l1:
            v1 = l1.val
            l1 = l1.next
        if l2:
            v2 = l2.val
            l2 = l2.next
        carry, val = divmod(v1+v2+carry, 10)
        n.next = ListNode(val)
        n = n.next
    return root.next

Built-in

  • divmod(a, b)

    Take two (non complex) numbers as arguments and return a pair of numbers consisting of their quotient and remainder when using integer division. With mixed operand types, the rules for binary arithmetic operators apply. For integers, the result is the same as (a // b, a % b). For floating point numbers the result is (q, a % b), where q is usually math.floor(a / b) but may be 1 less than that. In any case q * b + a % b is very close to a, if a % b is non-zero it has the same sign as b, and 0 <= abs(a % b) < abs(b).