LC 2 - Add Two Numbers

Question

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 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

Explanation: 342 + 465 = 807.

Example 2:

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

Example 3:

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

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.

Links

Question here and solution here

Solution

concept

We basically iterate through both list and add them up

1. need to take care of carry in each addition
2. if one of the list run out, we need to handle it by adding the other list to 0 (see NeetCode’s solution)
3. there is an edge case like 8 + 7 = 15 where we need to convert the carry to an extra digit, this is handled by the while condition in NeetCode’s solution.

code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	own implementation, very crude
	"""
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        cur_1 = l1
        cur_2 = l2
        dummy = ListNode(0)
        carry = False
        prev = dummy
		# add two list first
        while cur_1 and cur_2:
            _sum = cur_1.val + cur_2.val
            if carry:
                _sum += 1
            if _sum >= 10:
                val = _sum % 10
                carry = True
            else:
                val = _sum
                carry = False
            cur = ListNode(val)
            prev.next = cur
            prev = cur
            cur_1 = cur_1.next
            cur_2 = cur_2.next
		# handle the leftover of either one list
        if cur_1:
            while cur_1:
                _sum = cur_1.val
                if carry:
                    _sum += 1
                
                if _sum >= 10:
                    val = _sum%10
                    carry = True
                else:
                    val = _sum
                    carry = False
                cur = ListNode(val)
                prev.next = cur
                prev = cur
                cur_1 = cur_1.next
        elif cur_2:
            while cur_2:
                _sum = cur_2.val
                if carry:
                    _sum += 1
                
                if _sum >= 10:
                    val = _sum%10
                    carry = True
                else:
                    val = _sum
                    carry = False
                cur = ListNode(val)
                prev.next = cur
                prev = cur
                cur_2 = cur_2.next
		# handle edge cases where there is a final carry we need one more digit 1 infront.
        if carry:
            cur = ListNode(1)
            prev.next = cur
            cur.next = None

        return dummy.next

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        carry = 0

        while l1 or l2 or carry: # if both l1 and l2 are None, only carry is not None, it means the 8 + 7 = 15 case whre we need the extra digit for the carry.
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            # new digit
            val = v1 + v2 + carry
            carry = val // 10
            val = val % 10
            cur.next = ListNode(val)
            # update pointers
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next    

Complexity

time: $O(m+n)$
space: $O(1)$