Add Two Numbers
You're given the heads of two non-empty singly linked lists, each representing a non-negative integer. The digits are stored in reverse order, one digit per node, so the head holds the ones digit. Add the two numbers and return the sum as a linked list in the same reverse-digit form. Neither number has leading zeros, except the number 0 itself.
Examples
l1 = [6,1,7], l2 = [5,9,2] returns [1,1,0,1]
The lists hold 716 and 295, and 716 + 295 = 1011. The carry out of the hundreds place becomes a fourth node.
l1 = [9,9], l2 = [1] returns [0,0,1]
99 + 1 = 100. The carry ripples through both nines and adds a new node at the end.
l1 = [0], l2 = [4,3] returns [4,3]
0 + 34 = 34. Once the shorter list runs out, its missing digits count as 0.
Constraints
- 1 <= length of each list <= 100
- 0 <= Node.val <= 9
- Neither list has leading zeros, except the number 0 itself.
Hints
The digits are already in the order you'd add them by hand, starting from the ones place. What passes from one place to the next?
Walk both lists at once with a carry. A missing node in the shorter list counts as 0, and a dummy head saves you from special-casing the first digit.
Loop while l1, l2, or the carry remains: total = carry plus both digits, append a node with total % 10, set carry = total / 10, and advance whichever lists still have nodes. Return dummy.next.
Drill This: Your Approach First
Approach
The digits already come in the order you add them by hand, starting from the ones place. Walk both lists together with a carry. At each step, add the two current digits (0 for a list that has run out) plus the carry, append a node holding total % 10 after a tail pointer, and carry total / 10 forward. Keep going while either list has nodes or the carry is nonzero, so a final carry becomes its own node. A dummy head means the first digit needs no special case. O(max(m, n)) time and O(1) extra space beyond the output list.
Time
O(max(m, n))
Space
O(1) beyond the output
Pitfall
Solutions
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int total = carry;
if (l1 != null) {
total += l1.val;
l1 = l1.next;
}
if (l2 != null) {
total += l2.val;
l2 = l2.next;
}
tail.next = new ListNode(total % 10);
tail = tail.next;
carry = total / 10;
}
return dummy.next;
}
}from typing import Optional
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)
tail = tail.next
carry = total // 10
return dummy.next