[LeetCode] 2. Add Two Numbers

Table of Content

Problem Statement
Problem Input
Solution

Problem statement

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

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

Input

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':

Solution

Source code

Time Complexity: O(N)

Space Complexity: O(1)

The objective here is to take 2 numbers arranged as linked list and construct a final linked list representing the sum. The key to solve this problem is to understand carry, in which we transfer a digit from one digit to another. There are also 2 edge cases that we need to cover:

When the two linked list are not the same size.
When the sum of the last 2 digits produces a carry

To solve this problem, we will need to

Create a variable to help us keep track of the carry.
Initialize a output linked list, along with a variable as our reference iterator, so we don’t lose reference to the head of the linked list.
Iterate through both of the linked list. If one is shorter than the other, we’ll continue iterating through the larger one.
At the end of the loop, make sure to account for the edge case, where the sum of the last 2 digits produces a carry, which we handle by constructing a new ListNode with the value, 1. For example, two linked list, [5,5], [5,5], will output [0,1,1]. The last 1 in [0,1,1] is the result of the edge case.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
  def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
    # When any digit is greater than 10, we have to carry 1 over to the next digit.
    # We can hold this with a variable.
    # Example, when a node has the sum of 12, we carry 1 over to the next digit, and so the current digit would be 2
    carry = 0

    # Because we are guaranteed that both lists aren't empty. We can start calculating the first digit sum and set it as our first output node.
    digitSum = l1.val + l2.val
    output = ListNode(digitSum % 10)
    carry = 1 if digitSum >= 10 else 0
    # Move both iterators forward by one
    l1 = l1.next
    l2 = l2.next
    # We want to return the head of resulting list, which is output, so we can't use change output inside the while loop.
    # Therefore, we create a new variable to handle the iterating.
    digitIterator = output
    # Keep iterating until we reach the end of both list, aka when both are None
    while (l1 != None or l2 != None):
      # It is very possible that one list is shorter than the other list, so we can't perform an addition when we're already at the end of one list.
      if (l1 != None and l2 != None):
        digitSum = l1.val + l2.val
      elif (l1):
        digitSum = l1.val
      else:
        digitSum = l2.val
      # Need to add the carry to the digitSum
      digitSum += carry
      newDigitNode = ListNode(digitSum % 10)
      carry = 1 if digitSum >= 10 else 0
      # Set the current node's next as the new digit node
      # Advance the current node iterator onto the next node.
      digitIterator.next = newDigitNode
      digitIterator = digitIterator.next
      if (l1):
        l1 = l1.next
      if (l2):
        l2 = l2.next

    # There's an edge case we need to account for, in which the carry is 1, so we need to create a new Node for the carry.
    if (carry > 0):
      digitIterator.next = ListNode(1)
    return output

Complexity Explanation

Since we’re iterating through both linked list at the same time using only one while loop as well as constructing our final output, the time complexity is only O(N), where N is the size of the larger linked list.

Because we’ve only created two variables, one to hold number, and one as reference, the space complexity is only O(1) as they both taken up constant space.