Add Two Numbers
Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
l1 = 2→4→3, l2 = 5→6→47→0→8def add_two_numbers(l1, l2):
dummy = ListNode()
tail, carry = dummy, 0
while l1 or l2 or carry:
a = l1.val if l1 else 0
b = l2.val if l2 else 0
s = a + b + carry
carry, digit = divmod(s, 10)
tail.next = ListNode(digit)
tail = tail.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.nextfunction addTwoNumbers(l1, l2) {
const dummy = { val: 0, next: null };
let tail = dummy, carry = 0;
while (l1 || l2 || carry) {
const a = l1 ? l1.val : 0;
const b = l2 ? l2.val : 0;
const sum = a + b + carry;
carry = Math.floor(sum / 10);
tail.next = { val: sum % 10, next: null };
tail = tail.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
return dummy.next;
}class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int a = l1 != null ? l1.val : 0;
int b = l2 != null ? l2.val : 0;
int sum = a + b + carry;
carry = sum / 10;
tail.next = new ListNode(sum % 10);
tail = tail.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int a = l1 ? l1->val : 0;
int b = l2 ? l2->val : 0;
int sum = a + b + carry;
carry = sum / 10;
tail->next = new ListNode(sum % 10);
tail = tail->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
return dummy.next;
}Explanation
The digits are stored least significant first, which is exactly how we add numbers by hand: start from the ones place and carry leftward. So we can simply walk both lists from head to tail at the same time.
A dummy head node makes building the result clean — we always append to tail.next and return dummy.next at the end, avoiding special handling for the first node.
Each step we take a digit from each list (or 0 if that list ran out), add them plus the running carry, store sum % 10 in a new node, and set carry = sum // 10. The loop continues while either list has nodes left or there is a leftover carry.
Example: l1 = 2→4→3 (342) and l2 = 5→6→4 (465). 2+5=7, 4+6=0 carry 1, 3+4+1=8, giving 7→0→8 = 807.
The final carry matters: adding something like 9→9 would leave a carry that creates an extra leading node, which the carry condition in the loop handles automatically.