Add Two Numbers

problem at: https://leetcode.com/problems/add-two-numbers

# Definition for singly-linked list

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Solution

All the following solutions achieve a linear time complexity and constant space complexity.

# Add by ints

In the 1st while loop, calculate int sum by int addition.

In the 2nd while loop, construct ListNode ln w/ int modulus.

Please note that one modulus is calculated before 2nd while loop because Python has no do-while loop. However, there is some workaround.

Please refer to the next solution for the dummy head approach to avoid the do part before while loop.

Complexity:

  • Time:
  • Space:

where m is the number of nodes in l1 and n is the number of nodes in l2.

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    sum = 0
    power = 1

    while l1 or l2:
        l1_val = l1.val if l1!=None else 0
        l2_val = l2.val if l2!=None else 0
        sum += l1_val*power + l2_val*power
        power *= 10
        l1 = l1.next if l1!=None else None
        l2 = l2.next if l2!=None else None

    # sum transformed from int to ListNode
    ln = ListNode(sum%10)
    sum = sum//10
    end = ln
    while sum:
        node = ListNode(sum%10)
        sum = sum//10
        end.next = node
        end = end.next
    return ln

# DIY ListNode Adder

Rather than adding by ints, we could DIY a ListNode adder to achieve simpler code (avoid the 2nd while loop and used the dummy head instead of do before while loop).

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = end = ListNode(0)
    sum = 0
    carry = 0

    while l1 or l2 or carry:
        l1_val = l1.val if l1!=None else 0
        l2_val = l2.val if l2!=None else 0
        sum = l1_val + l2_val + carry
        end.next = ListNode(sum%10)
        carry = sum//10
        end = end.next
        l1 = l1.next if l1!=None else None
        l2 = l2.next if l2!=None else None

    return dummy.next

# While Loop (REDO)

The if {foo}!=None then {bar} thing looks quite ugly. We could achieve even cleaner code using a while loop with 2 if statements.

???