The problem
Two non-negative whole numbers are stored as linked lists, one digit per node, with the ones digit first: 342 is the list 2 → 4 → 3. Return their sum as a list in the same form.
Neither number has leading zeros, except the number 0 itself.
Examples
01
- Input
l1 = [2, 4, 3], l2 = [5, 6, 4]
- Output
[7, 0, 8]
02
- Input
l1 = [0], l2 = [0]
- Output
[0]
03
- Input
l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
- Output
[8, 9, 9, 9, 0, 0, 0, 1]
Constraints
- 1 ≤ nodes in each list ≤ 100
- 0 ≤ Node.val ≤ 9
The idea
This is addition as taught at school, column by column from the ones — and the lists already hand over the digits in that order.
Walk both lists together. In each column add the two digits (0 if a list has ended) and the carry from the column before: the new digit is sum mod 10 and the carry is sum ÷ 10, rounded down. Keep going while either list has digits or the carry is 1 — 5 + 5 needs a last node for the 1 in 10.
- Time
- O(max(n, m)) — one column per digit
- Space
- O(max(n, m)) — the answer’s digits
Solution · every language run against every case
class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = tail = ListNode() carry = 0 while l1 or l2 or carry: total = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0) carry, digit = divmod(total, 10) # e.g. 17 -> carry 1, digit 7 tail.next = ListNode(digit) tail = tail.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None return dummy.next