445. Add Two Numbers II
On LeetCode ->Problem¶
Add two non-empty linked lists where each node is one digit and digits are stored most-significant first; return the sum in the same format, without leading zeros.
- Example:
Key trick¶
Use stacks or recurse from the tail so you can add digits right-to-left while keeping the output in forward order.
Trap¶
- Adding only while both lists exist and then appending the rest is wrong because carry must keep propagating.
- Reversing inputs is fine for the basic problem, but the follow-up asks to avoid it.
- Converting to Python integers works here in Python, but it is usually not the intended linked-list technique.
Why is it interesting?¶
It tests how to simulate grade-school addition when the list order is the opposite of the natural processing order.
Python solution¶
from typing import Optional
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# Push digits so we can add from least significant to most significant
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
carry = 0
head = None
# Build result from back to front by prepending nodes
while s1 or s2 or carry:
total = carry
if s1:
total += s1.pop()
if s2:
total += s2.pop()
carry, digit = divmod(total, 10)
head = ListNode(digit, head)
return head
Comment on my solution¶
- Your first reverse-based attempt fails because after the common part ends, it attaches the remaining nodes directly without adding the carry through them.
- It also forgets to append a final carry like
999 + 1 -> 1000. - Your integer-conversion solution passes in Python and is short, but interviewers often prefer a true linked-list solution because it matches the follow-up idea and avoids relying on big integers.
# WRONG - Doesn't pass leetcode tests
# First attempt (reversing lists)
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
def reverse_list(l):
prev = None
cur = l
while cur:
nxt = cur.next # save tail before rewiring
cur.next = prev # reverse pointer
prev = cur # grow reversed prefix
cur = nxt # continue forward
return prev
l1 = reverse_list(l1)
l2 = reverse_list(l2)
sum = ListNode()
dummy = sum
decimal = 0
while l1 and l2:
v1, v2 = l1.val, l2.val
l1, l2 = l1.next, l2.next
n = v1 + v2 + decimal
new_decimal = n // 10
digit = n % 10
sum.next = ListNode(digit)
sum = sum.next
decimal = new_decimal
if l1:
sum.next = l1
if l2:
sum.next = l2
return reverse_list(dummy.next)
# OK - Pass leetcode test
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
def reverse_list(l):
prev = None
cur = l
while cur:
nxt = cur.next # save tail before rewiring
cur.next = prev # reverse pointer
prev = cur # grow reversed prefix
cur = nxt # continue forward
return prev
num1 = 0
while l1:
num1 = num1 * 10 + l1.val
l1 = l1.next
num2 = 0
while l2:
num2 = num2 * 10 + l2.val
l2 = l2.next
sum = num1 + num2
digit = sum % 10
sum = sum // 10
sum_list = ListNode(digit)
head_sum = sum_list
while sum:
digit = sum % 10
sum = sum // 10
sum_list.next = ListNode(digit)
sum_list = sum_list.next
return reverse_list(head_sum)
# OK - Written after reading AI comments
class Solution:
def addTwoNumbers(self, l1, l2) -> Optional[ListNode]:
stack1 = []
stack2 = []
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
stack_sum = []
dec = 0
while stack1 or stack2 or dec:
d1 = stack1.pop() if stack1 else 0
d2 = stack2.pop() if stack2 else 0
n = d1 + d2 + dec
dec = n // 10
digit = n % 10
stack_sum.append(digit)
sum = ListNode()
dummy = sum
while stack_sum:
sum.next = ListNode(stack_sum.pop())
sum = sum.next
return dummy.next
divmod(32, 10) # (3, 2)
divmod(8, 10) # (0, 8)
divmod(3, 2) # (1, 1)
divmod(2, 2) # (1, 0)