 See the easier related problem Add Two Numbers.

## # Solution

Among the following solutions, 1st solution is easiest to think of but need to know how to reverse a singly linked list by heart. 2nd solution could be thought of when LIFO rings a bell. last solution could be thought of but takes time to implement.

Create a nested function reverseList to reverse the two input linked list and then construct a ListNode adder, similar as before.

Complexity:

• Time:
• Space: due to no extra 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:
def reverseList(l: ListNode) -> ListNode:
prev = None
curr = l

while curr:
# IMPT: remember the steps to reverse a singly linked list!!!
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev

new_l1 = reverseList(l1)
new_l2 = reverseList(l2)

carry = 0
end = dummy = ListNode(0)
while new_l1 or new_l2 or carry:
if new_l1:
carry += new_l1.val
new_l1 = new_l1.next
if new_l2:
carry += new_l2.val
new_l2 = new_l2.next
end.next = ListNode(carry%10)
end = end.next
carry = carry//10

return reverseList(dummy.next)


What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

There are two ways: stack and recursion.

### # Stack

Initialize two stacks for l1 and l2 respectively: l1_stack and l2_stack. After appending, I then pop each stack and calculate the sum. Note that now sum is also reversed, so the way to construct is different from previous question.

Complexity:

• Time:
• Space: due to extra space of 2 stacks
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
l1_stack = []
l2_stack = []

while l1:
l1_stack.append(l1.val)
l1 = l1.next
while l2:
l2_stack.append(l2.val)
l2 = l2.next

l1_len = len(l1_stack)
l2_len = len(l2_stack)

i = j = 0
carry = 0

while i<l1_len or j<l2_len or carry:
if i<l1_len:
carry += l1_stack.pop()
i += 1
if j<l2_len:
carry += l2_stack.pop()
j += 1
temp = ListNode(carry%10)
carry //= 10



### # Recursion (REDO!)

Frankly, I copied most of the following code, as the recursive function add_list is not easy to write(especially what vars to return). The idea is:

1. get the difference in length of l1 and l2
2. IMPT: recursively add two lists and return head and new_carry. Note that diff decreases only when ln1 is longer than ln2
3. if there is a leftmost carry, make it head and return

Complexity:

• Time:
• Space: due to implicit stack space
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
def get_len(l: ListNode) -> int:
length = 0
while l:
l = l.next
length += 1
return length

def add_lists(ln1: ListNode, ln2: ListNode, diff: int) -> (ListNode, int):
if ln1 is None and ln2 is None:
return None, 0
if diff>0:
# currently ln1 is longer than ln2
# move the pointer at list1 to n1.next, don't move the pointer at list2
next_node, carry = add_lists(ln1.next, ln2, diff-1)
carry += ln1.val
else:
next_node, carry = add_lists(ln1.next, ln2.next, diff)
carry += ln1.val + ln2.val
new_val, new_carry = carry%10, carry//10

l1_len, l2_len = get_len(l1), get_len(l2)
# always keep len(ln1) > len(ln2)
if l1_len < l2_len:
l1_len, l2_len = l2_len, l1_len
l1, l2 = l2, l1
diff = l1_len - l2_len