2. Add Two Numbers

https://leetcode.com/problems/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 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.

Strategy

So my strategy is to first base my solution on how I receive my input, and what output I should be generating. So knowing that my input is never going to be empty, I don't have to worry about that test case. As well as that, the input is always positive, which makes everything a lot easier. In addition, the number represented by the linked lists do not contain any leading zeroes - so no stripping will have to be done (but casting to an int would resolve this anyway).

So to strategise, I basically make a checklist of how I want to first process the input. The easiest way to generate the sum, is to convert the linked list inputs into numbers first (integers) and that allows me to sum them up very easily. From there, I can look into how I can convert the result of the addition to a linked list which I return.

Converting Input to a Number

So given the two inputs are of the form: L1: (digit_0, digit_10, digit_100) and L1: (digit_0, digit_10, digit_100)

What I need to do is as follows:

• Create a list to store the number

• Iterate through the Linked List

• Append the digits to the list (node.value attribute)

• Reverse when done

Once I've done this, I will have two list variables which contain the complete numbers in the correct order that correspond to L1 and L2.

# Create lists to store the numbers
list1 = []
list2 = []

# Iterate through Linked List 
curr = L1
while curr:
    list1.append(curr.val)  # Append digits to the list
    curr = curr.next

curr = L2
while curr:
    list2.append(curr.val)  # Append digits to the list
    curr = curr.next

# list1: [d0, d10, d100]
# list2: [d0, d10, d100]
# Reverse the list when done
list1.reverse()  # list1: [3, 4, 2]
list2.reverse()  # list2: [4, 6, 5]

Converting the Lists to Integers and doing the Math

At this stage, we have our lists where we want them; containing the digits of the number in order. Now all we need to do is convert them into a number and add for the desired result. This takes a bit of manipulation in the following steps, due to the restrictions of some of the functions.

• Convert all list items to be strings (as they are currently integers)

• Join the list to be one string

• Convert the joint string to be an integer

• Add the two numbers

After this, we will have a variable containing the sum of the two numbers that were given as inputs.

# Convert list items to strings
list1 = list(map(str, list1)  # ['3', '4', '2']
list2 = list(map(str, list2)  # ['4', '6', '5']

# Join the list to be one string
num1 = ''.join(list1)  # '342'
num2 = ''.join(list1)  # '465'

# Convert joint string to become an integer
num1 = int(num1)  # 342
num2 = int(num2)  # 465

# Add the two numbers
result = num1 + num2  # 807 = 342 + 465

Obtaining the result as a Linked List and Returning

Finally, the last step of this problem is to take the result, split it up to digits and convert it to a linked list which we can return. Breaking this up, we have a checklist as such:

• Convert result into a string

• Convert result into a list (splits number into digits)

• Reverse the order of the list

• Convert all items to a number

• Create a linked list which we can return

• Iterate through the digits and save as nodes in the linked list

# Convert result into string: '807'
result = str(result)

# Convert result into list: ['8', '0', '7']
result = list(result)

# Reverse list: ['7', '0', '8']
result.reverse()

# Convert all items to a number
result = list(map(int, result))

# Create a linked list to return
l3 = ListNode(result.pop(0))

# Iterate through digits and save in linked list
curr = l3
while result:  # as long as result has digits
    curr.next = ListNode(result.pop(0))
    curr = curr.next
    
return l3

Solution

Putting all of this together, we can obtain a solution that looks like:

def addTwoNumbers(l1, l2):
    # Convert inputs to lists
    num1 = []
    curr = l1
    while curr:
        num1.append(curr.val)
        curr = curr.next
        
    num2 = []
    curr = l2
    while curr:
        num2.append(curr.val)
        curr = curr.next
        
    # Reverse order and convert to numbers
    num1.reverse()
    num2.reverse()
    
    num1 = int(''.join(map(str, num1)))
    num2 = int(''.join(map(str, num1)))
    
    # Obtain the sum and convert result to a list
    result = num1 + num2
    result = list(str(result))
    result.reverse()
    result = list(map(int, result))
    
    # Convert list to a linked list and return
    l3 = ListNode(result.pop(0))
    curr = l3
    while result:
        curr.next = ListNode(result.pop(0))
        curr = curr.next
        
    return l3

Better Solution

Given the inputs as they are, they are in optimal order for us to be able to calculate their sum just like we would on paper. In this case, we simply need something to store the carry, and thereby iteratively we calculate and append nodes to the linked list which we are returning.