Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order. Add the two numbers and return the sum as a linked list.
Example
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
342 + 465 = 807.Solution
Walk both lists simultaneously, summing digits and propagating carry. Use a dummy head to simplify.
def add_two_numbers(l1, l2):
dummy = ListNode(0)
curr = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
total = v1 + v2 + carry
carry = total // 10
curr.next = ListNode(total % 10)
curr = curr.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.nextfunction addTwoNumbers(l1, l2) {
const dummy = { next: null };
let curr = dummy, carry = 0;
while (l1 || l2 || carry) {
const v1 = l1 ? l1.val : 0;
const v2 = l2 ? l2.val : 0;
const total = v1 + v2 + carry;
carry = Math.floor(total / 10);
curr.next = { val: total % 10, next: null };
curr = curr.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
return dummy.next;
}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* curr = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int v1 = l1 ? l1->val : 0;
int v2 = l2 ? l2->val : 0;
int total = v1 + v2 + carry;
carry = total / 10;
curr->next = new ListNode(total % 10);
curr = curr->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
return dummy.next;
}public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry > 0) {
int v1 = l1 != null ? l1.val : 0;
int v2 = l2 != null ? l2.val : 0;
int total = v1 + v2 + carry;
carry = total / 10;
curr.next = new ListNode(total % 10);
curr = curr.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}Complexity
- Time: O(max(n, m))
- Space: O(max(n, m))
Explanation
Reverse-order digits make addition natural — process from least significant digit. The loop continues while either list has nodes OR there’s a carry to write.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?