2. Add Two Numbers

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 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.

Discussion

The main logic of this algorithm is simple: Mathematical addition digit by digit, with digits in linked lists. Yet there are tricky points to be handled:

1. When two numbers have different numbers of significant figures,
2. When carry digits exist in the addition, and
3. When the most significant figures of the sum is carry.

Solution

Solving 1, when there is 1 linked list running out of nodes during addition, we proceed the addition with the missing digits replaced by 0.

Solving 2, we cache any carry digit in each iteration, and pass the digit to the next digital addition. The remainder of the digital sum is saved in the result linked list. Thus every iteration perform addition as: carry(0/1) + value_1 + value_2

Solving 3, we perform similar addition in 1, check and handle 2 after the last iteration.

# 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: ListNode, l2: ListNode) -> ListNode:
        result = ListNode(0)
        node = result

        while (l1 and l1.next) or (l2 and l2.next):
            s = node.val

            if l1:
                s += l1.val
            if l2:
                s += l2.val

            node.val = s % 10
            node.next = ListNode(s//10)

            l1 = l1.next or ListNode(0)
            l2 = l2.next or ListNode(0)
            node = node.next

        if l1:
            node.val += l1.val

        if l2:
            node.val += l2.val

        if node.val >= 10:
            node.val = node.val % 10
            node.next = ListNode(1)

        return result

Complexity Analysis

• Time Complexity: O(max(m, n)), wheres m and n are the size of the two input list. As only one looping through the larger input linked list is required.
• Space Complexity: O(max(m, n)), as the result linked list's size is determined by the larger input linked list.