445. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.
Follow-Up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
Solution: Two Stacks, O(n) space
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
stack1 = self.get_vals(l1)
stack2 = self.get_vals(l2)
root = None
carry = 0
while stack1 or stack2 or carry > 0:
if stack1:
carry += stack1.pop()
if stack2:
carry += stack2.pop()
node = ListNode(carry % 10)
node.next = root
root = node
carry /= 10
return root
def get_vals(self, node):
vals = []
while node:
vals.append(node.val)
node = node.next
return vals
Solution: Recursion, O(n) stack space
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
len1 = self.get_len(l1)
len2 = self.get_len(l2)
root = self.add(l1, l2, len1, len2)
if root.val >= 10:
root, node = ListNode(root.val // 10), root
node.val %= 10
root.next = node
return root
def add(self, l1, l2, len1, len2):
if len1 == len2 == 0:
return None
if len1 > len2:
root = ListNode(l1.val)
root.next = self.add(l1.next, l2, len1 - 1, len2)
elif len1 < len2:
root = ListNode(l2.val)
root.next = self.add(l1, l2.next, len1, len2 - 1)
else:
root = ListNode(l1.val + l2.val)
root.next = self.add(l1.next, l2.next, len1 - 1, len2 - 1)
if root.next and root.next.val >= 10:
root.val += root.next.val // 10
root.next.val %= 10
return root
def get_len(self, node):
length = 0
while node:
length += 1
node = node.next
return length
Solution: O(1) space
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
len1 = self.get_len(l1)
len2 = self.get_len(l2)
# make sure l1 is longer
if len1 < len2:
l1, l2 = l2, l1
len1, len2 = len2, len1
# pre is the last node before cur whose value is not 9
root = pre = cur = ListNode(0)
# align l1 and l2
while len1 > len2:
cur.next = ListNode(l1.val)
if cur.val < 9:
pre = cur
cur = cur.next
l1 = l1.next
len1 -= 1
# add l1 and l2
while l1:
cur.next = ListNode(l1.val + l2.val)
if cur.val < 9:
pre = cur
cur = cur.next
l1 = l1.next
l2 = l2.next
if cur.val >= 10:
cur.val %= 10
pre.val += 1
while pre.next != cur:
pre = pre.next
pre.val = 0
return root if root.val else root.next
def get_len(self, node):
length = 0
while node:
length += 1
node = node.next
return length
Lessons:
- Remember the last node before current node whose value is not 9, so when current node has a carry, just add 1 to that last node, and change every node's value to 0 in between.