You get two non-empty linked lists l1 and l2. Each one stores a non-negative integer with its digits in reverse order, one digit per node (the head holds the ones digit). Return the sum of the two numbers as a linked list in the same reversed format. Neither number has leading zeros, except the number 0 itself.
342 + 465 = 807, stored in reverse as 7, 0, 8.- 1 <= number of nodes in each list <= 100
- 0 <= Node.val <= 9
- No leading zeros except the number 0
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A tempting brute force converts both lists to integers, adds them and converts back. That breaks for 100-digit numbers in Java or C++ because they overflow every built-in type. The lists are already in the order of school addition (ones digit first), so we can add column by column, carrying into the next node, and build the answer while we walk. A dummy head keeps the appending code simple.
Algorithm
- Create a dummy node and a
tailpointer, and setcarry = 0. - Loop while
l1,l2orcarryis non-zero. - Add the current digits (0 for a finished list) and
carry. - Append a node with
sum % 10, setcarry = sum / 10, and advance the pointers. - Return
dummy.next.
O(max(m, n))Space: O(max(m, n)) for the output list, O(1) extracarry in the loop condition handles cases like [5] + [5] = [0,1] without a special check after the loop. A common follow-up is the forward-order version (Add Two Numbers II): use two stacks or reverse the lists first.class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0) tail = dummy carry = 0 while l1 or l2 or carry: total = carry if l1: total += l1.val l1 = l1.next if l2: total += l2.val l2 = l2.next tail.next = ListNode(total % 10) # current digit tail = tail.next carry = total // 10 # carry into the next column return dummy.next