Description

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

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

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

Problem definition

• Function:add two numbers
• Input: list1, a linked list, list2, a linked list
• Precondition: 0<|list1| < 100, |list 2| > 0, 0 ≤ node.value ≤ 9, 0< list1[0] ≤ 9, 0< list2[0] ≤ 9
• Output: sum, a linked list
• Postcondition: $sum[0] \times 10^0 + sum[1] x 10^1 ... + sum[| sum | - 1] \times 10^{| list1 | - 1} = list1[0] x 10^0 + list1[1] \times 10^1 ... + list1[| list1 | - 1] \times 10^{| list1 | - 1} + list2[0] \times 10^0 + list2[1] \times 10^1 ... + list2[| list2 | - 1] x 10^{| list2 | - 1}$

The outline of the algorithm

• This question can be divided into two parts: 1. calculate the sum of the two linked lists and 2. convert the sum into a linked list.
• I solve this in a recursive style

The first part

• Function: sum of a list
• Input: list1, a linked list, degree, an integer
• Precondition: 0 < |list1| < 100, 0 ≤ node.value ≤ 9, 0< list1[0] ≤ 9
• Output: sum, an integer
• Postcondition: $sum = list1[0] \times 10^{degree} + list1[1] \times 10^{degree + 1} ... + list1[| list1 | - 1] \times 10^{degree + | list1 |}$

• Let's think about the base case: The lowest possible input is there is only one node in the linked list, which means its next value is None. In this case, we multiply the value of the current pointing node by 10 to the power of nodes we travel
• What about other cases: we multiply the value of the current pointing node by 10 to the power of nodes we travel, I use degree to denote it and + call the function on the next node

• The recursive definition is:
  • if n is the last node: node.value x $10^{degree}$
  • otherwise: node.value x $10^{degree}$ + sum of a list(node.value, degree + 1).

• For the complexity, in each recursive call, we calculate the node.value x 10^{degree} which has a complexity of O(\log degree)
• number of recursive call x complexity of each call = $( | list1 | \times O(\log degree)) = O ( | list1 | \times \log degree)$ . Since the degree is increased by 1 for everyone more linked list, so it is also $O(\log |list1|)$ .
• The code

def sum_of_a_list(node, degree = 0):
        if node.next == None:
            return node.val * 10 ** degree
        else:
            return node.val * 10 ** degree + sum_of_a_list(node.next, degree + 1)

The second part

• this part is to create a linked list from the sum of the two linked list
• Function: new linked list
• Input: sum, an integer
• Precondition: an int ≥ 0
• Output: list3, a linked list
• Postcondition: $sum = list3[0] \times 10^{0} + list3[1] \times 10^{1} ... + list3[| list3 | - 1] \times 10^{| list3 |}$

The outline of the algorithm

• I would assign one digit to one node starting from the last digit of the sum, the last digit can be found by the remainder sum divided by 10. Every time I assign a digit, I will shift the end pointer to the left by shortening the sum using floor division by 10. Since in this implementation, there is no head pointer to the first node of the linked list, I have to explicitly create a first node variable to assign the last digit of the sum and pass the rest of sum to the recursive function.

• The base case of the reclusive approach would be the sum becoming 0. The sum will only become 0 when both linked lists have only a 0 value node or after the floor division a single digit, which means the last digit of the sum. The former situation is handled by the creation of the first node variable. In the latter situation, since there is no leading 0 in the sum, so we don't need to assign this 0, so we will assign the value of this node to be None.
• In other cases: we assign the last digit of the sum and then cut the last digit of the sum and assign the node.next value to the next node
• The recursive definition is:
  • if sum = 0: node.val = none
  • if sum > 0:
    • current node.val = sum % 10
    • sum = sum // 10
    • current node.next = new linked list(sum)

• The complexity is basically affected by the number of digits of sum, i.e. $O((\log_{10} sum) + 1) = O (\log sum)$ . Since sum is larger when the two linked list given in the first place is longer, so this also mean it has a complexity of O(log l list1|).
• The code

def new_linked_list(sum:int):
  def in_new_linked_list(an_int2:int):
            if an_int2 == 0:
                return None
            else:
                current_node = ListNode()
                current_node.val = an_int2 % 10
                an_int2 = an_int2 // 10
                current_node.next = in_new_linked_list(an_int2)
                return current_node

        first_node = ListNode(sum % 10)
        sum = sum // 10
        first_node.next = in_new_linked_list(sum)
        return first_node 

Combined algorithm

1. let sum be the sum of list1 and the sum of list 2
2. convert sum to a linked list
3. let first node be the linked list of sum

• The overall complexity is $O (( | list1 | \times \log | list1 |) + \log | list1 | )$ = O (( | list1 | x \log | list1 |). Since we are concerned only with the fastest growing term. This means the overall complexity is a log-linear complexity.
• The Code

def addTwoNumbers(l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    def sum_of_a_list(node, degree = 0):
        if node.next == None:
            return node.val * 10 ** degree
        else:
            return node.val * 10 ** degree + sum_of_a_list(node.next, degree + 1)

    # degree = 0
    sum = sum_of_a_list(l1,0) + sum_of_a_list(l2, 0)

    def new_linked_list(sum:int):
        def in_new_linked_list(an_int2:int):
            if an_int2 == 0:
                return None
            else:
                current_node = ListNode()
                current_node.val = an_int2 % 10
                an_int2 = an_int2 // 10
                current_node.next = in_new_linked_list(an_int2)
                return current_node

        first_node = ListNode(sum % 10)
        sum = sum // 10
        first_node.next = in_new_linked_list(sum)
        return first_node   

    return new_linked_list(sum)

Feeling

• - Actually, I am quite happy to finish this challenge, although this is a slow algorithm. This is the first time, I successfully write a recursive algorithm outside of the course material. This give me more confidence and experience to write recursive algorithms which I am a bit confused about before.

Reference:

Add Two Numbers - LeetCode